Sort List

Problem: Sort List

We can use merge list to sort the list. We first split list into two parts and sort these two lists and then merge them. By doing this recursively, we can sort the list.

Code in Python:

class Solution(object):
    def merge(self, list1, list2):
        head = tail = ListNode(None)
        while list1 and list2:
            if list1.val < list2.val:
                tail.next, tail, list1 = list1, list1, list1.next
            else:
                tail.next, tail, list2 = list2, list2, list2.next
        tail.next = list1 or list2
        return head.next

    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        fast = slow = head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        slow.next, slow = None, slow.next
        list1 = self.sortList(head)
        list2 = self.sortList(slow)
        return self.merge(list1, list2)