class UserList:
    """ A user defined singly linked list"""
    def __init__(self):
        self.head = None
        self.tail = None


    def __str__(self):
        """ String function """
        s = '['
        h = self.head
        while h != None:
            s += str(h.data)
            h = h.next
            if h != None:
                s += ', '
        s += ']'
        return s
    
    def insert_after(self, node):
        """ Insert a node with data at the end of the list
        """
        if self.is_empty():   # the node will be the first one in list
            self.head = node
            self.tail = node
        else:                 # insert after the current tail
            self.tail.next = node
            self.tail = node

    def insert_before(self, node):
        """ Insert a node with data before the head of the list
        """
        if self.is_empty():   # the node will be the first one in list
            self.head = node
            self.tail = node
        else:                 # insert before the current head
            node.next = self.head
            self.head = node

    def remove_node(self, target):
        """ Remove the node containing the target
        """
        prev = None
        cur  = self.head
        while cur != None and cur.data != target:
            prev = cur
            cur  = cur.next

        if cur != None:    # found it and remove it
            if cur == self.head:
                self.head = cur.next  # head is removed, reset head
            else:
                prev.next = cur.next  # remove a middle node
            
    def is_empty(self):
        """ Return True if the list is empty, False otherwise.
        """
        return self.head == None

    def search(self, target ):
        """ Return the node that contains the 'target'
        or None if the taget is not in the list.
        """
        prev = None
        cur_node = self.head
        while cur_node != None and cur_node.data != target :
            prev = cur_node
            cur_node= cur_node.next
 
        #return cur_node, prev
        return cur_node

    def search_swap(self, target ):
        """ Return the node that contains the 'target'
        or None if the taget is not in the list.
        """
        prev = None
        cur_node = self.head
        while cur_node != None and cur_node.data != target :
            prev = cur_node
            cur_node= cur_node.next
 
        return prev, cur_node

    def swap_nodes(self, x, y):
        """ Swap two nodes holding values x and y
        """
        prev1, node1 = self.search_swap(x)
        prev2, node2 = self.search_swap(y)
        if node1 is None or node2 is None:
            return
        
        if prev1 != None:
            prev1.next = node2
        else:
            self.head = node2
            
        if prev2 != None:
            prev2.next = node1
        else:
            self.head = node1
            
        temp = node1.next
        node1.next = node2.next
        node2.next = temp
        
        if node2.next == None:
            self.tail = node2
        elif node1.next == None:
            self.tail = node1

    def find_before(self, node):
        """ Find the pointer before the node
        """
        if node == None:
            return None
        temp = self.head
        prev = None
        while temp != None and temp != node:
            prev = temp
            temp = temp.next
        return prev
    
    def sort_list(self):
        """ Sort a list into ascending order. Do that's similar to
        bubblesort. Assume all values are distinct.
        """
        
        end = self.tail
        while end != self.head:
            # print(self)
            temp = self.head
            x = temp.data
            large=temp
            while temp != end.next:
                if x < temp.data:
                    x = temp.data
                    large=temp
                temp = temp.next
            # print('swapping ', large.data, end.data)   
            if large!=end:
                self.swap_nodes(large.data, end.data)
            prev = self.find_before(large)
            #print('now find before')
            #print('==end', end.data)
            #print('end prev', end.data, prev.data)
            end = prev
            
        
    def insert_sorted(self, node):
        """ Insert a new node into a sorted list. Node has value in it.
        """
        prev, place = self.find_place(node)
        if prev is None:   # insert as a new head
            node.next = self.head.next
            self.head = node
        elif place is None:  # insert after tail
            self.tail.next = node
            self.tail = node
        else:
            prev.next = node
            node.next = place
        
    def find_place(self, node):
        """ Find where the right place for the node in a sorted list
        """
        prev = None
        cur  = self.head
        while cur != None and cur.data < node.data:
            prev = cur
            cur = cur.next
        return prev, cur
      
class ListNode:
    """ The node class for list notes"""
    def __init__(self, data):
        self.data = data
        self.next = None