Merge K Sorted Lists

Problem

Merge k sorted linked lists and return one sorted list.

Key insight: Min-heap of (value, list_index, node). Pop minimum, push next node from same list.

Solutions

// C — use min-heap of node values

// C++
ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode* a, ListNode* b){ return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> minH(cmp);
    for (auto l : lists) if (l) minH.push(l);
    ListNode dummy(0);
    ListNode* cur = &dummy;
    while (!minH.empty()) {
        cur->next = minH.top(); minH.pop();
        cur = cur->next;
        if (cur->next) minH.push(cur->next);
    }
    return dummy.next;
}

// Java
public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> minH = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
    for (ListNode l : lists) if (l != null) minH.offer(l);
    ListNode dummy = new ListNode(0), cur = dummy;
    while (!minH.isEmpty()) {
        cur.next = minH.poll();
        cur = cur.next;
        if (cur.next != null) minH.offer(cur.next);
    }
    return dummy.next;
}

// JavaScript
function mergeKLists(lists) {
    // Use sorted approach for simplicity
    const nodes = [];
    for (let l of lists) while (l) { nodes.push(l.val); l = l.next; }
    nodes.sort((a, b) => a - b);
    const dummy = new ListNode(0);
    let cur = dummy;
    for (const v of nodes) { cur.next = new ListNode(v); cur = cur.next; }
    return dummy.next;
}

# Python
import heapq

def mergeKLists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    dummy = ListNode(0)
    cur = dummy
    while heap:
        val, i, node = heapq.heappop(heap)
        cur.next = node
        cur = cur.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

Complexity

Time: O(N log k) where N = total nodes, k = number of lists
Space: O(k)

Key Insight

The heap always contains at most one node from each list. Each of N nodes is pushed/popped once: O(N log k).

Tie-break: Include list index i in tuple to avoid comparing ListNode objects when values are equal.