Python O(nlogn) time, O(1) space solution with explanation


  • 0

    Merge Sort: Sort every 2 elements from head to tail, then start again from head, sort every 4 elements, and so on.

    So I start with k = 1, which means sort every 2 elements (k elements in my first list, and some elements <= k in my second list), then I sort again with k = k*2, etc, until my first list has k or more elements, then I know we're finished.

    In order to sort every 2*k elements, I just merge sort them. The only hard part here is to get the heads of the 2 lists and merge them. That is implemented in the function getHeads(head, k), where head is the head of the first list of the pair of list we want to merge.

    The algorithm sounds simple, but it took me a while to make it correct in my code. Here it is:

    class Solution(object):
        # Get head and tail of list1 and list 2 with k elements
        # If there is not enough elements, we just cut there and
        # leave them NULL
        def getHeads(self, head, k):
            h1, t1, h2, t2, nextHead = head, None, None, None, None
            t = h1
            count = 1
            while t and t.next and count < k:
                count += 1
                t = t.next
            t1 = t
            if t1:
                h2 = t.next
                t = t.next
            count += 1
            while t and t.next and count < 2*k:
                count += 1
                t = t.next
            t2 = t
            if t2:
                nextHead = t.next
            return h1, t1, h2, t2, nextHead
        
        # Merge 2 sorted LinkedLists and return their merged list's head and tail
        def merge(self, h1, t1, h2, t2):
            fakeHead = ListNode(0)
            t = fakeHead
            while h1 and h2:
                if h1.val <= h2.val:
                    t.next = h1
                    h1 = h1.next
                else:
                    t.next = h2
                    h2 = h2.next
                t = t.next
            if h1:
                t.next = h1
                newTail = t1
            else:
                t.next = h2
                newTail = t2
            return fakeHead.next, newTail
            
        def sortList(self, head):
            fakeHead = ListNode(0)
            fakeHead.next = head
            tmp = fakeHead
            k = 1
            h1, t1, h2, t2, nextHead = self.getHeads(head, k)
            while h2:
                tmp = fakeHead
                while h2:
                    if t1: t1.next = None
                    if t2: t2.next = None
                    mergeHead, mergeTail = self.merge(h1, t1, h2, t2)
                    tmp.next = mergeHead
                    tmp = mergeTail
                    h1, t1, h2, t2, nextHead = self.getHeads(nextHead, k)
                tmp.next = h1
                k *= 2
                h1, t1, h2, t2, nextHead = self.getHeads(fakeHead.next, k)
            return fakeHead.next
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.