Python code with O(nlogn) time and O(1) space with natural merge sort


  • 0
    F

    The algorithm is described on Wikipedia.

    Basically it is similar to a merge sort in bottom-up manner. In each stage, I try to find two adjacent non-decreasing "runs" and merge them. We are done if we have only run left.

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
    
        # @param two ListNodes
        # @return a ListNode
        def mergeTwoLists(self, l1, l2):
            head = ListNode(0)
            tail = head
            
            while True:
                if not l1:
                    tail.next = l2
                    break
                if not l2:
                    tail.next = l1
                    break
                if l1.val > l2.val:
                    l1,l2 = l2,l1
                    
                tail.next = l1
                tail = l1
                l1 = l1.next
                tail.next = None
            
            while tail.next:
                tail = tail.next
            return head.next, tail
        
        def findRun(self, head):
            if not head:
                return None
            if not head.next:
                return head
            
            last = head
            p = head.next
            while p:
                if p.val < last.val:
                    break
                else:
                    last = p
                    p = p.next
            return last
            
            
        def natural_mergesort(self, head):
            
            # calculate the length
            n = 0
            p = head
            while p:
                p = p.next
                n += 1
            
            # already done
            if n <= 1:
                return head
    
            while True:
                t1 = self.findRun(head)
                h1 = head
                if not t1.next:
                    # already sorted
                    return h1
                tail = None
                
                while t1.next:
                    # we have more than one sublist
                    h2 = t1.next
                    t2 = self.findRun(h2)
                    h3 = t2.next
                    
                    t1.next = None
                    t2.next = None
                    newh, newt = self.mergeTwoLists(h1, h2)
                    if not tail:
                        # this is the first pair of runs in this stage
                        head, tail = newh, newt
                    else:
                        tail.next = newh
                        tail = newt
                        
                    if not h3:
                        # no runs any more
                        h1 = t1 = None
                        break
                    else:
                        h1 = h3
                        t1 = self.findRun(h3)
                if t1:
                    # we still have one last run
                    tail.next = h1
                    tail = t1
                    
        
        # @param head, a ListNode
        # @return a ListNode
        def sortList(self, head):
            
            return self.natural_mergesort(head)
    

  • 0
    I

    how much time does your solution consume?


Log in to reply
 

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