Merge K Sorted Lists

hard Linked List

You are given an array of k linked lists, each sorted in ascending order. Merge all k lists into a single sorted linked list and return the head. The total number of nodes across all lists can be up to 10^4, and k can be up to 10^4. Lists may be empty.

Example

lists = [[1, 4, 5], [1, 3, 4], [2, 6]]

Output: [1, 1, 2, 3, 4, 4, 5, 6]

All three sorted lists are combined into a single sorted list. Every element from every input list appears exactly once in the output, in non-decreasing order.

Use a min-heap (priority queue) to efficiently find the smallest element across all k lists at each step. Start by pushing the head node of every non-empty list into the heap. Pop the smallest node, add it to the result, and if that node has a next pointer, push the next node back into the heap. Repeat until the heap is empty.

Why this works

You need the smallest element across k lists at each step. Comparing all k heads every time would be slow. A min-heap keeps the k heads organized so you can extract the minimum in O(log k) time instead of O(k), making the overall algorithm much faster.

Step by step

Seed the heap — push the head of each non-empty list into the min-heap. The heap now holds at most k nodes.
Pop the smallest — the heap gives you the global minimum across all k lists in O(log k) time.
Append to result — attach the popped node to your growing merged list.
Push the successor — if the popped node has a next node, push it into the heap so that list stays represented.
Repeat until empty — when the heap is empty, all nodes have been merged in sorted order.

Time: O(n * log k) Space: O(k)

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>(
            (a, b) -> a.val - b.val  // min-heap ordered by node value
        );
        for (ListNode node : lists) {
            if (node != null) {
                heap.offer(node);
            }
        }
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while (!heap.isEmpty()) {
            ListNode node = heap.poll();  // always grab the global minimum
            curr.next = node;
            curr = curr.next;
            if (node.next != null) {
                heap.offer(node.next);  // push next from same list
            }
        }
        return dummy.next;
    }
}

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto cmp = [](ListNode* a, ListNode* b) {
            return a->val > b->val;  // min-heap: smaller values have higher priority
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> heap(cmp);
        for (ListNode* node : lists) {
            if (node) {
                heap.push(node);
            }
        }
        ListNode dummy(0);
        ListNode* curr = &dummy;
        while (!heap.empty()) {
            ListNode* node = heap.top();
            heap.pop();  // always grab the global minimum
            curr->next = node;
            curr = curr->next;
            if (node->next) {
                heap.push(node->next);  // push next from same list
            }
        }
        return dummy.next;
    }
};

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

import heapq

def mergeKLists(lists: list[Optional[ListNode]]) -> Optional[ListNode]:
    dummy = ListNode(0)
    curr = dummy
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))  # i breaks ties between equal values
    while heap:
        val, i, node = heapq.heappop(heap)  # always grab the global minimum
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))  # push next from same list
    return dummy.next