Merge k Sorted Lists

Problem Statement

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:

[
  1->4->5,
  1->3->4,
  2->6
]

merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:
Input: lists = []
Output: []

Example 3:
Input: lists = [[]]
Output: []

Approach: Divide and Conquer (Pairwise Merge)

A brute-force approach would be to merge the first list with the second, then merge the result with the third, and so on. However, this is inefficient.

Instead, we can use a Divide and Conquer strategy, very similar to Merge Sort. We pair up the k lists and merge each pair. This reduces the number of lists from $k$ to $k/2$. We repeat this process until only one sorted list remains.

Because we already know how to merge two sorted lists in $O(N)$ time, we can simply reuse that logic!

1. Edge Cases: If the lists array is empty, return null.
2. Iterative Merging:
   • Loop as long as lists.length > 1.
   • Create a temporary array mergedLists to hold the results of this current “round” of merges.
   • Iterate through lists taking two lists at a time (i and i + 1).
   • Merge these two lists using the standard “Merge Two Sorted Lists” algorithm.
   • Push the resulting merged list into mergedLists.
   • (Note: If there’s an odd number of lists, the last list is just pushed to mergedLists as-is and will be merged in the next round).
   • Once the inner loop finishes, overwrite lists with mergedLists.
3. When the outer loop finishes, lists[0] will contain our final, fully merged linked list.

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
function mergeKLists(lists) {
    if (!lists || lists.length === 0) return null;
    
    // Continue merging pairs until only 1 list remains
    while (lists.length > 1) {
        let mergedLists = [];
        
        // Take lists 2 at a time
        for (let i = 0; i < lists.length; i += 2) {
            let l1 = lists[i];
            let l2 = (i + 1 < lists.length) ? lists[i + 1] : null;
            
            mergedLists.push(mergeTwoLists(l1, l2));
        }
        // Update lists array for the next round
        lists = mergedLists;
    }
    
    return lists[0];
}

// Standard helper function to merge two sorted lists
function mergeTwoLists(l1, l2) {
    let dummy = new ListNode();
    let tail = dummy;
    
    while (l1 !== null && l2 !== null) {
        if (l1.val < l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    
    if (l1 !== null) tail.next = l1;
    if (l2 !== null) tail.next = l2;
    
    return dummy.next;
}

Complexity Analysis

• Time Complexity: $O(N \log k)$ where $N$ is the total number of nodes across all lists, and $k$ is the number of linked lists. In each round of merging, we process every single node once (which takes $O(N)$ time). Since we divide the number of lists in half each round, there are $O(\log k)$ rounds.
• Space Complexity: $O(\log k)$ or $O(k)$ auxiliary space for the mergedLists array we create in each iteration. (If we did the merging completely in-place by reusing the input array slots, it could be reduced to $O(1)$).