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

  • 0

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

  • 0

    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.