合并 K 个升序链表
题目要求
你需要处理一个链表数组，其中每个链表的元素都是按照升序排列的。你的任务是将这些链表合并成一个新的、同样按照升序排列的单一链表，并返回这个合并后的链表。
解题思路
要解决这个问题，你可以遵循以下步骤：
-
初始化：创建一个新的链表头节点，用于存放合并后的链表。同时，维护一个指针，用于指向当前合并链表的最后一个节点。
-
比较头节点：比较所有链表的头节点，找出最小的节点。这一步可以通过建立一个最小堆（优先队列）来实现，以便高效地获取当前最小节点。
-
链接节点：将找到的最小节点链接到合并链表的末尾，并将该节点所在链表的头指针移动到下一个节点。
-
重复步骤：重复步骤 2 和步骤 3，直到所有链表都被完全遍历，即所有链表的头节点都变为 null。
-
返回结果：返回初始化时创建的新链表头节点的下一个节点，因为头节点是一个空节点，用于方便操作。
这个问题的关键在于如何高效地找到当前最小的节点。使用最小堆可以在 O(logn)的时间复杂度内完成这一操作（n 是链表的数量）。每次操作后，你需要更新堆，这样才能在下一次比较时获取正确的最小节点。当所有链表都遍历完毕时，你就得到了一个完整的、升序排列的链表。
Golang 版本
package main
import (
"container/heap"
)
// ListNode is the definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
// MinHeap is a min-heap of ListNodes.
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[0 : n-1]
return x
}
func mergeKLists(lists []*ListNode) *ListNode {
minHeap := &MinHeap{}
heap.Init(minHeap)
// Add the head of each list to the min heap
for _, list := range lists {
if list != nil {
heap.Push(minHeap, list)
}
}
// Create a dummy head for the result list
dummy := &ListNode{}
current := dummy
// Extract the smallest element from the heap and add it to the result list
for minHeap.Len() > 0 {
smallest := heap.Pop(minHeap).(*ListNode)
current.Next = smallest
current = current.Next
if smallest.Next != nil {
heap.Push(minHeap, smallest.Next)
}
}
return dummy.Next
}
func main() {
// Example usage:
// Assume we have an array of linked-list heads `lists`
// mergedList := mergeKLists(lists)
// Print or process the merged list as needed
}
这段代码定义了一个最小堆，并使用标准库中的 heap 接口来管理这个堆。mergeKLists 函数首先将每个链表的头节点加入到最小堆中。然后，它不断从堆中取出最小元素，将其加入到结果链表中，并将该元素的下一个节点（如果存在）加入到堆中。这个过程一直持续到堆为空，即所有链表的节点都已经被处理。最后，函数返回合并后的链表的头节点。
C++版本
#include <iostream>
#include <vector>
#include <queue>
// Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
struct compare {
bool operator()(const ListNode* l1, const ListNode* l2) {
return l1->val > l2->val;
}
};
ListNode* mergeKLists(std::vector<ListNode*>& lists) {
std::priority_queue<ListNode*, std::vector<ListNode*>, compare> pq;
// Initialize the priority queue with the head of each list
for (ListNode* list : lists) {
if (list) pq.push(list);
}
// Create a new head for the merged list
ListNode dummy(0);
ListNode* tail = &dummy;
// Keep pulling the smallest item from the heap and add it to the merged list
while (!pq.empty()) {
tail->next = pq.top();
pq.pop();
tail = tail->next;
if (tail->next) pq.push(tail->next);
}
return dummy.next;
}
int main() {
// Example usage:
// Assume we have a vector of ListNode pointers `lists`
// ListNode* mergedList = mergeKLists(lists);
// Print or process the merged list as needed
}
这段代码使用 C++ 的 priority_queue 来实现最小堆，以维护当前最小节点。mergeKLists 函数首先将每个链表的头节点加入到最小堆中。然后，它不断从堆中取出最小元素，将其加入到结果链表中，并将该元素的下一个节点（如果存在）加入到堆中。这个过程一直持续到堆为空，即所有链表的节点都已经被处理。最后，函数返回合并后的链表的头节点。
Python 版本
from heapq import heappush, heappop
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# The `__lt__` method is necessary for the ListNode to be put in a heap
def __lt__(self, other):
return self.val < other.val
def merge_k_lists(lists):
min_heap = []
# Initialize the heap
for head in lists:
if head:
heappush(min_heap, head)
# Create a dummy node to start the merged list
dummy = ListNode(0)
current = dummy
# Extract the smallest node from the heap and add it to the merged list
while min_heap:
node = heappop(min_heap)
current.next = node
current = current.next
if node.next:
heappush(min_heap, node.next)
return dummy.next
# Example usage:
# lists = [ListNode(1), ListNode(2), ListNode(3)] # Replace with actual lists
# merged_list = merge_k_lists(lists)
# Print or process the merged list as needed
这段代码首先定义了一个 ListNode 类，用于表示链表节点，并实现了 __lt__ 方法，以便节点可以被放入 Python 的 heapq 模块提供的最小堆中。merge_k_lists 函数使用最小堆来合并链表。它首先将所有链表的头节点放入堆中，然后不断从堆中取出最小节点，并将其添加到合并后的链表中。如果取出的节点后面还有节点，就将下一个节点放入堆中。当堆为空时，所有链表都已合并完毕，函数返回合并后链表的头节点。
Java 版本
import java.util.PriorityQueue;
// 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; }
}
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, (a, b) -> a.val - b.val);
// Add the first node of each list to the priority queue
for (ListNode node : lists) {
if (node != null) {
queue.add(node);
}
}
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!queue.isEmpty()) {
tail.next = queue.poll();
tail = tail.next;
if (tail.next != null) {
queue.add(tail.next);
}
}
return dummy.next;
}
}
// Example usage:
// Solution solution = new Solution();
// ListNode[] lists = new ListNode[] { /* initialize your lists here */ };
// ListNode mergedList = solution.mergeKLists(lists);
// Print or process the merged list as needed.
这段代码使用 Java 的 PriorityQueue 类来实现最小堆，以维护当前最小节点。mergeKLists 方法首先检查输入数组是否为空，然后将每个链表的头节点加入到优先队列中。然后，它不断从队列中取出最小元素，将其加入到结果链表中，并将该元素的下一个节点（如果存在）加入到队列中。这个过程一直持续到队列为空，即所有链表的节点都已经被处理。最后，方法返回合并后的链表的头节点。
Rust 版本
#![allow(unused)] fn main() { use std::cmp::Ordering; use std::collections::BinaryHeap; // Definition for singly-linked list. #[derive(PartialEq, Eq, Clone)] pub struct ListNode { pub val: i32, pub next: Option<Box<ListNode>>, } impl ListNode { #[inline] fn new(val: i32) -> Self { ListNode { next: None, val } } } // To use ListNode in a BinaryHeap, we need to implement Ord and PartialOrd. impl Ord for ListNode { fn cmp(&self, other: &Self) -> Ordering { // Flip the ordering here because BinaryHeap is a max heap, // but we want to use it as a min heap. other.val.cmp(&self.val) } } impl PartialOrd for ListNode { fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(self.cmp(other)) } } pub fn merge_k_lists(lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> { let mut heap = BinaryHeap::new(); // Push the first node of each list into the heap. for list in lists { if let Some(node) = list { heap.push(node); } } // Take the smallest element from the heap and add it to the result list. let mut head = Some(Box::new(ListNode::new(0))); let mut tail = &mut head; while let Some(mut node) = heap.pop() { if let Some(next) = node.next.take() { heap.push(next); } tail.as_mut().unwrap().next = Some(node); tail = &mut tail.as_mut().unwrap().next; } head.unwrap().next } // Example usage: // let lists = vec![Some(Box::new(ListNode::new(1))), Some(Box::new(ListNode::new(2))), Some(Box::new(ListNode::new(3)))]; // Replace with actual lists // let merged_list = merge_k_lists(lists); // Print or process the merged list as needed. }
在这个 Rust 版本的代码中，我们首先定义了一个 ListNode 结构体来表示链表节点，并为其实现了 Ord 和 PartialOrd trait，这样我们就可以将 ListNode 存入 BinaryHeap 中。由于 BinaryHeap 是一个最大堆，我们在比较函数中反转了顺序，使其表现得像一个最小堆。
merge_k_lists 函数接受一个 ListNode 的 Vec<Option<Box<ListNode>>>，将每个链表的头节点放入堆中，然后不断从堆中取出最小节点，并将其添加到结果链表中。如果取出的节点后面还有节点，就将下一个节点放入堆中。当堆为空时，所有链表都已合并完毕，函数返回合并后链表的头节点。
总结
上面给出的解法使用了堆（优先队列）来合并多个已排序链表。无论是使用 Python、Java、C++、Rust 还是 Golang，基本思路都是一致的：将每个链表的头节点加入到堆中，然后不断从堆中取出最小节点，将其加入到结果链表中，并将该元素的下一个节点（如果存在）加入到堆中。这个过程一直持续到堆为空，即所有链表的节点都已经被处理。这种方法的时间复杂度为 O(Nlogk)，其中 N 是所有链表中元素的总和，k 是链表的个数。