Python3 Bottom-Up, In-Place Merge Sort

  • 0
    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)
   = new_head
            prev_tail = new_tail
    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:
                curr =
            tail = curr
            curr = if curr is not None else None
            if tail is not None:
       = 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:
       = head_b
                head_b =
            elif head_b is None:
       = head_a
                head_a =
            elif head_a.val <= head_b.val:
       = head_a
                head_a =
       = head_b
                head_b =
            tail = = None
        return, tail
    def list_len(head):
        len_ = 0
        while head is not None:
            len_ += 1
            head =
        return len_

Log in to reply

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