23. Merge k Sorted Lists

Problem Link

We've previously solved Merging two sorted linked lists efficiently in linear time. However, this problem requires merging k sorted lists, and a naive approach of merging them one by one would lead to unnecessary repeated work and higher time complexity. Instead, we can apply a divide-and-conquer strategy, similar to the merge step in merge sort. Instead of merging all lists sequentially, we merge them in pairs, reducing the number of lists by half at each step.

Initially, all k lists are stored in an array. While more than one list remains:

• We iterate through the array in steps of two.
• Merge each adjacent pair of lists.
• Store the merged results in a temporary array.

If the number of lists is odd, the last list is carried forward as-is. After each pass, the total number of lists is reduced roughly by half. This process continues until only one merged list remains, which is returned as the final result.

Each node is processed once per merge level, and the number of merge levels is \(O(logk)\). This ensures the total time complexity stays optimal.

Runtime Complexity

Time: \(O(Nlogk)\), where \(N\) is the total number of nodes across all lists, \(k\) is number of lists

Space: \(O(k)\)

PythonGo

from typing import List, Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists or len(lists) == 0:
            return None

        def merge(l1, l2):
            curr = dummy = ListNode()
            while l1 and l2:
                if l1.val > l2.val:
                    curr.next = l2
                    l2 = l2.next
                else:
                    curr.next = l1
                    l1 = l1.next
                curr = curr.next
            if l1:
                curr.next = l1
            if l2:
                curr.next = l2
            return dummy.next

        while len(lists) > 1:
            temp = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i+1] if i+1 < len(lists) else None
                temp.append(merge(l1, l2))
            lists = temp
        return lists[0]

func mergeKLists(lists []*ListNode) *ListNode {
    var l1, l2 *ListNode
    for len(lists) > 1 {
        temp := make([]*ListNode, 0)
        for i := 0; i < len(lists); i += 2 {
            l1 = lists[i]
            l2 = nil
            if i+1 < len(lists) {
                l2 = lists[i+1]
            }
            temp = append(temp, mergeTwoLists(l1, l2))
        }
        lists = temp
    }
    return lists[0]
}

---