https://leetcode.com/problems/sort-list

This is pretty straightforward question, if you know how to use merge sort. All we need to do is to split our list into two parts, sort the first half, then sort the second half and finally merge this two parts. Here I use two axuilary function:

  1. getMid(head), which will find the middle of list with given head and cut it into two smaller lists. We use the idea of slow and fast pointers here to find middle efficiently.
  2. merge(head1, head2) will merge two lists with given heads. To make it more readible and to avoid corner cases, it is good idea to use dummy sentinel node in the beginning of list. We iterate over two lists, using two pointers and add them one by one. When we out of nodes, we attach the rest of on of the lists to the end, we return the start of our new list.
  3. sortList(head): it is our original function: if list has length 0 or 1, we do not do anything, it is corner case of our recursion. If it is not the case, we find mid = self.getMid(head), which will cut our list into two smaller lists and return the start of the second list. Finally, we apply sortList() to head and to mid and merge two parts.

Complexity: Time complexity is O(n log n), because it is classical complexity of merge sort. Space complexity is O(log n), because we use recursion which can be log n deep.

class Solution:
    def sortList(self, head):
        if not head or not head.next: return head
        mid = self.getMid(head)
        left = self.sortList(head)
        right = self.sortList(mid)
        return self.merge(left, right)
    
    def getMid(self, head):
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        mid = slow.next
        slow.next = None
        return mid
    
    def merge(self, head1, head2):
        dummy = tail = ListNode(None)
        while head1 and head2:
            if head1.val < head2.val:
                tail.next, tail, head1 = head1, head1, head1.next
            else:
                tail.next, tail, head2 = head2, head2, head2.next
    
        tail.next = head1 or head2
        return dummy.next

Follow up question askes us to do it in O(1) memory, and it is possible to do it, using bottom-up merge sort, which is much more difficult to implement during interview limits. What I expect that if you just explain the idea, without implementing this will be already quite good. So, idea is the following: imagine, that we have list a1, a2, a3, a4, a5, a6, a7, a8. Let us first sort values in pairs: (a1, a2), (a3, a4), (a5, a6), (a7, a8). then we sort values in groups by 4, mergin our pairs: (a1, a2, a3, a4), (a5, a6, a7, a8). And finally we merge them in one group of 9. It is more difficult to implement and I will add code later.

If you like the solution, you can upvote it on leetcode discussion section: Problem 0148