The challenge
Merge k sorted lists into a single sorted chain, reusing their nodes.
Inputs are sorted, acyclic, and pairwise disjoint. N is their total node count.
Example
[1, 4], [2, 5], [3, 6] → [1, 2, 3, 4, 5, 6].
Use the walkthrough below to inspect the input and each state change.
See Merge k lists, step by step
Follow the pointers. Watch each link change.
A1headAA1headBB1headCC1Inspect node links
| Node | Value | Next |
|---|---|---|
| A1 | 1 | A2 |
| A2 | 4 | null |
| B1 | 2 | B2 |
| B2 | 5 | null |
| C1 | 3 | C2 |
| C2 | 6 | null |
Read the input
IDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links.
Start from the input head pointers.View original input
A: 1 (A1) → 4 (A2); B: 2 (B1) → 5 (B2); C: 3 (C1) → 6 (C2); parameters: {}
Parameter indices are zero-based, except n from the end, which is one-based. Node IDs remain fixed when links change.
Put it into code
The smallest available front is always the next output node.
Node stores val and next; the random-pointer lesson adds random. C++ uses C++17 or later.
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
import heapq
from itertools import count
def merge_k(lists):
heap, serial = [], count()
for head in lists:
if head:
heapq.heappush(heap, (head.val, next(serial), head))
dummy = Node()
tail = dummy
while heap:
_, _, node = heapq.heappop(heap)
nxt = node.next
tail.next = node
tail = node
if nxt:
heapq.heappush(heap, (nxt.val, next(serial), nxt))
tail.next = None
return dummy.next
#include <cstddef>
#include <queue>
#include <vector>
struct Node {
int val;
Node* next;
Node(int value = 0, Node* link = nullptr)
: val(value), next(link) {}
};
Node* merge_k(const std::vector<Node*>& lists) {
auto greater = [](Node* a, Node* b) {
return a->val > b->val;
};
std::priority_queue<Node*, std::vector<Node*>,
decltype(greater)> heap(greater);
for (Node* head : lists) if (head) heap.push(head);
Node dummy;
Node* tail = &dummy;
while (!heap.empty()) {
Node* node = heap.top();
heap.pop();
Node* next = node->next;
tail->next = node;
tail = node;
if (next) heap.push(next);
}
tail->next = nullptr;
return dummy.next;
}