LeetCode 23: Merge k Sorted Lists (Min-Heap on List Heads)
LeetCode 23HeapLinked ListK-Way MergeToday we solve LeetCode 23 - Merge k Sorted Lists.
Source: https://leetcode.com/problems/merge-k-sorted-lists/
English
Problem Summary
Given an array of k sorted linked lists, merge them into one sorted linked list and return its head.
Key Insight
This is a classic k-way merge. At any moment, the next smallest node must be one of the current list heads. So we push each non-null head into a min-heap and always pop the smallest one.
Brute Force and Limitations
A naive approach is to collect all values into an array, sort, and rebuild a list: O(N log N) time and extra memory. Another approach merges lists one by one, which can degrade to O(Nk).
Optimal Algorithm Steps
1) Initialize a min-heap ordered by node value.
2) Push every non-null list head into heap.
3) Use a dummy head + tail pointer for result list.
4) While heap is not empty: pop min node, append to result, then push its next (if exists).
5) Return dummy.next.
Complexity Analysis
Let N be total node count and k be number of lists. Each node is pushed/popped once from heap of size up to k, so time is O(N log k). Heap space is O(k).
Common Pitfalls
- Forgetting to skip null heads when initializing heap.
- Not advancing tail after appending node.
- Comparator overflow in languages using subtraction (prefer safe comparator).
- Returning dummy instead of dummy.next.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* 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> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
for (ListNode head : lists) {
if (head != null) pq.offer(head);
}
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
tail.next = node;
tail = tail.next;
if (node.next != null) pq.offer(node.next);
}
return dummy.next;
}
}type ListNode struct {
Val int
Next *ListNode
}
type MinHeap []*ListNode
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) {
*h = append(*h, x.(*ListNode))
}
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
func mergeKLists(lists []*ListNode) *ListNode {
h := &MinHeap{}
heap.Init(h)
for _, head := range lists {
if head != nil {
heap.Push(h, head)
}
}
dummy := &ListNode{}
tail := dummy
for h.Len() > 0 {
node := heap.Pop(h).(*ListNode)
tail.Next = node
tail = tail.Next
if node.Next != nil {
heap.Push(h, node.Next)
}
}
return dummy.Next
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* 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;
};
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
for (auto node : lists) {
if (node) pq.push(node);
}
ListNode dummy(0);
ListNode* tail = &dummy;
while (!pq.empty()) {
ListNode* node = pq.top();
pq.pop();
tail->next = node;
tail = tail->next;
if (node->next) pq.push(node->next);
}
return dummy.next;
}
};# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
import heapq
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = ListNode(0)
tail = dummy
while heap:
_, i, node = heapq.heappop(heap)
tail.next = node
tail = tail.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next// Minimal binary min-heap for ListNode by val
class MinHeap {
constructor() {
this.arr = [];
}
size() { return this.arr.length; }
push(node) {
this.arr.push(node);
this._up(this.arr.length - 1);
}
pop() {
if (!this.arr.length) return null;
const top = this.arr[0];
const last = this.arr.pop();
if (this.arr.length) {
this.arr[0] = last;
this._down(0);
}
return top;
}
_up(i) {
while (i > 0) {
const p = (i - 1) >> 1;
if (this.arr[p].val <= this.arr[i].val) break;
[this.arr[p], this.arr[i]] = [this.arr[i], this.arr[p]];
i = p;
}
}
_down(i) {
const n = this.arr.length;
while (true) {
let s = i;
const l = i * 2 + 1;
const r = i * 2 + 2;
if (l < n && this.arr[l].val < this.arr[s].val) s = l;
if (r < n && this.arr[r].val < this.arr[s].val) s = r;
if (s === i) break;
[this.arr[s], this.arr[i]] = [this.arr[i], this.arr[s]];
i = s;
}
}
}
var mergeKLists = function(lists) {
const heap = new MinHeap();
for (const node of lists) {
if (node) heap.push(node);
}
const dummy = new ListNode(0);
let tail = dummy;
while (heap.size() > 0) {
const node = heap.pop();
tail.next = node;
tail = tail.next;
if (node.next) heap.push(node.next);
}
return dummy.next;
};中文
题目概述
给定一个由 k 个有序链表组成的数组，请将它们合并为一个有序链表并返回头结点。
核心思路
这是典型的 k 路归并。每一轮的最小节点只可能出现在当前各链表的头结点里，因此维护一个按节点值排序的小根堆即可高效取最小值。
暴力解法与不足
暴力方案可以把所有节点值取出后整体排序再重建链表，时间 O(N log N) 且需要额外空间。若按顺序两两合并，也可能退化到 O(Nk)。
最优算法步骤
1）建立按节点值比较的小根堆。
2）把每个非空链表头结点入堆。
3）使用虚拟头结点 dummy 和尾指针 tail。
4）循环：弹出堆顶最小节点并接到结果链表；若该节点有 next，则把 next 入堆。
5）返回 dummy.next。
复杂度分析
设总节点数为 N，链表数量为 k。每个节点最多入堆/出堆各一次，堆大小最多为 k，时间复杂度 O(N log k)，额外空间复杂度 O(k)。
常见陷阱
- 初始化堆时忘记过滤空链表。
- 拼接节点后忘记移动 tail。
- 比较器直接做减法导致潜在溢出（应使用安全比较）。
- 返回 dummy 而不是 dummy.next。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* 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> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
for (ListNode head : lists) {
if (head != null) pq.offer(head);
}
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
tail.next = node;
tail = tail.next;
if (node.next != null) pq.offer(node.next);
}
return dummy.next;
}
}type ListNode struct {
Val int
Next *ListNode
}
type MinHeap []*ListNode
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) {
*h = append(*h, x.(*ListNode))
}
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
func mergeKLists(lists []*ListNode) *ListNode {
h := &MinHeap{}
heap.Init(h)
for _, head := range lists {
if head != nil {
heap.Push(h, head)
}
}
dummy := &ListNode{}
tail := dummy
for h.Len() > 0 {
node := heap.Pop(h).(*ListNode)
tail.Next = node
tail = tail.Next
if node.Next != nil {
heap.Push(h, node.Next)
}
}
return dummy.Next
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* 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;
};
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
for (auto node : lists) {
if (node) pq.push(node);
}
ListNode dummy(0);
ListNode* tail = &dummy;
while (!pq.empty()) {
ListNode* node = pq.top();
pq.pop();
tail->next = node;
tail = tail->next;
if (node->next) pq.push(node->next);
}
return dummy.next;
}
};# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
import heapq
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = ListNode(0)
tail = dummy
while heap:
_, i, node = heapq.heappop(heap)
tail.next = node
tail = tail.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next// Minimal binary min-heap for ListNode by val
class MinHeap {
constructor() {
this.arr = [];
}
size() { return this.arr.length; }
push(node) {
this.arr.push(node);
this._up(this.arr.length - 1);
}
pop() {
if (!this.arr.length) return null;
const top = this.arr[0];
const last = this.arr.pop();
if (this.arr.length) {
this.arr[0] = last;
this._down(0);
}
return top;
}
_up(i) {
while (i > 0) {
const p = (i - 1) >> 1;
if (this.arr[p].val <= this.arr[i].val) break;
[this.arr[p], this.arr[i]] = [this.arr[i], this.arr[p]];
i = p;
}
}
_down(i) {
const n = this.arr.length;
while (true) {
let s = i;
const l = i * 2 + 1;
const r = i * 2 + 2;
if (l < n && this.arr[l].val < this.arr[s].val) s = l;
if (r < n && this.arr[r].val < this.arr[s].val) s = r;
if (s === i) break;
[this.arr[s], this.arr[i]] = [this.arr[i], this.arr[s]];
i = s;
}
}
}
var mergeKLists = function(lists) {
const heap = new MinHeap();
for (const node of lists) {
if (node) heap.push(node);
}
const dummy = new ListNode(0);
let tail = dummy;
while (heap.size() > 0) {
const node = heap.pop();
tail.next = node;
tail = tail.next;
if (node.next) heap.push(node.next);
}
return dummy.next;
};
Comments