ll

class ListNode:
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

    def __repr__(self):
        return repr(self.data)


class LinkedList:
    def __init__(self):
        self.head = None

    def print(self):
        nodes = []
        curr = self.head

        while curr:
            nodes.append(repr(curr))
            curr = curr.next

        return nodes

    def prepend(self, data):
        self.head = ListNode(data=data, next=self.head)

    def append(self, data):
        if not self.head:
            self.prepend(data)

        cur = self.head
        while cur.next:
            cur = cur.next

        newNode = ListNode(data)
        cur.next = newNode

    def insert_middle(self, data):
        """
        o(logn)
        :param data:
        :return:
        """
        if self.head is None:
            self.prepend(data)
            return

        slow = self.head
        fast = self.head

        if fast.next is None:
            self.append(data)
            return

        fast = fast.next.next

        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next

        newNode = ListNode(data, slow.next)
        slow.next = newNode


    def deleteend(self):
        """
        o(n)
        :return:
        """
        cur = self.head
        while cur.next.next:
            cur = cur.next

        cur.next = None





ll = LinkedList()
print(ll.print())
ll.insert_middle(1)
print(ll.print())
ll.insert_middle(2)
print(ll.print())
ll.insert_middle(3)
print(ll.print())
ll.insert_middle(4)
print(ll.print())
ll.deleteend()
print(ll.print())
ll.insert_middle(5)
print(ll.print())