Python3 Bottom-Up, In-Place Merge Sort


  • 0
    B
    import math
    
    
    class Solution:
        def sortList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            if head is None:
                return head
            length = list_len(head)
            levels = math.ceil(math.log(float(length), 2))
            for level in range(levels):
                head = split_and_merge(head, 2 ** level)
            return head
                
    
    def split_and_merge(head, size):
        list_pairs = iter_list_pairs(head, size)
        sentinel = ListNode(float('inf'))
        prev_tail = sentinel
        for head_a, head_b in iter_list_pairs(head, size):
            new_head, new_tail = merge_lists(head_a, head_b)
            prev_tail.next = new_head
            prev_tail = new_tail
        return sentinel.next
        
        
    def iter_list_pairs(head, size):
        sublists = split_list(head, size)
        return iter(
            lambda: (next(sublists, None), next(sublists, None)),
             (None, None)
        )
       
    
    def split_list(head, size):
        while head is not None:
            curr = head
            for i in range(size - 1):
                if curr is None:
                    break
                curr = curr.next
            tail = curr
            curr = curr.next if curr is not None else None
            if tail is not None:
                tail.next = None
            yield head
            head = curr
            
        
    def merge_lists(head_a, head_b):
        tail = sentinel = ListNode(float('-inf'))
        while head_a is not None or head_b is not None:
            if head_a is None:
                tail.next = head_b
                head_b = head_b.next
            elif head_b is None:
                tail.next = head_a
                head_a = head_a.next
            elif head_a.val <= head_b.val:
                tail.next = head_a
                head_a = head_a.next
            else:
                tail.next = head_b
                head_b = head_b.next
            tail = tail.next
        tail.next = None
        return sentinel.next, tail
        
            
    def list_len(head):
        len_ = 0
        while head is not None:
            len_ += 1
            head = head.next
        return len_
    

Log in to reply
 

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