Python Bottom up Mergesort O(1) space


  • 0
        def sortList(self, head):
    
            size = 0
            itr = head
            while itr:
                size, itr = size + 1, itr.next
            lng = 1
            buffr = ListNode(None)
            buffr.next = head
            while lng < size:
                p = buffr # initialize
                l = r = buffr.next
                while l:
                    val = lng
                    while r and val > 0:
                        r, val = r.next, val - 1
                    if not r: break
                    lc = rc = lng
                    #similar to merging 2 sorted lists. difference is that, 
                    #we're actually dealing with 2 different sections of a long list
                    while l and r and lc and rc: 
                        if l.val < r.val: 
                            p.next, p, l, lc = l, l, l.next, lc - 1
                        else:
                            p.next, p, r, rc = r, r, r.next, rc - 1
                    if lc or not r: # trailing elements in left segment
                        while lc > 1: # move left ptr until last of its segment
                            p.next = p = l
                            l, lc = l.next, lc - 1
                        p.next = p = l # update p to last of lc
                        l.next = r
                    else: # trailing elements in right segment
                        while r and rc:
                            p.next = p = r
                            r, rc = r.next, rc - 1
                    l = r
                lng *= 2
            return buffr.next
    

Log in to reply
 

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