#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/divide-and-conquer/merge-k-sorted-lists-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/divide-and-conquer/merge-k-sorted-lists-implementation

Repovive

Merge k Sorted Lists - Implementation - Divide and Conquer | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Merge k Sorted Lists - Implementation

Here is the implementation:

function mergeKLists(lists):
    if lists is empty:
        return null
    return mergeRange(lists, 0, lists.length - 1)

function mergeRange(lists, left, right):
    if left == right:
        return lists[left]

    mid = (left + right) / 2
    l1 = mergeRange(lists, left, mid)
    l2 = mergeRange(lists, mid + 1, right)
    return mergeTwoLists(l1, l2)

function mergeTwoLists(l1, l2):
    dummy = new ListNode()
    curr = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    curr.next = l1 or l2
    return dummy.next

$O(N \log k)$ time, $O(\log k)$ space for recursion.