#P4051. 合并K个升序链表
-
ID: 2293
Tried: 87
Accepted: 19
Difficulty: 6
合并K个升序链表
题目内容
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表
输入描述
第一行为一个整数k， 接下来的k行，每行若干个整数，以空格隔开，表示一个链表节点的值。
输出描述
输出共一行，包含排序后链表节点的值，用空格隔开。
样例1
输入
3
1 4 5
1 3 4
2 6
输出
1 1 2 3 4 4 5 6
说明
[ 1−>4−>5, 1−>3−>4, 2−>6 ] 将它们合并到一个有序链表中得到。 1−>1−>2−>3−>4−>4−>5−>6
提示
- k==lists.length
- 0<=k<=104
- 0<=lists[i].length<=500
- −104<=lists[i][j]<=104
- lists[i] 按升序 排列
- lists[i].length 的总和不超过 104
合并 k 个升序链表
题解思路
本题要求将多个已排序的链表合并成一个升序的链表。每个链表中的元素都已经排好序，我们需要利用这些已排序链表的信息将其合并为一个新的有序链表。
方法一：使用最小堆（优先队列）
最小堆是一种数据结构，它支持在对元素进行插入和删除时，始终保持堆顶元素为最小值。我们可以利用最小堆来实现这个问题。
思路：
-
初始化最小堆：首先，我们将所有链表的头节点放入最小堆中。堆中的元素会按节点的值排序。这样，堆顶元素就是当前最小的节点。
-
逐步合并：每次从最小堆中弹出一个节点，将它加入到结果链表中，然后将弹出节点的下一个节点（如果存在）加入堆中。这样，堆中始终保持着当前最小的节点，直到所有链表都被合并完。
-
时间复杂度分析：插入堆和删除堆顶元素的时间复杂度是 O(log k)，其中 k 是链表的数量。每个节点最多会被操作一次，假设总节点数为 n，则总体时间复杂度为 O(n log k)。
方法二：两两合并
我们还可以采用两两合并的方法来解题。首先将两个链表合并成一个有序链表，然后再将结果与下一个链表合并，直到所有链表合并完。
思路：
-
两两合并：首先选择两个链表进行合并，得到一个有序链表。然后将该链表与下一个链表合并，再得到一个新的有序链表。重复这一过程，直到所有链表都合并到一起。
-
时间复杂度分析：每次合并两个链表的时间复杂度是 O(n)，其中 n 是链表中的节点数。由于最多需要合并 k 次，整体的时间复杂度为 O(k * n)。
Python 代码实现(方法一)
import heapq
# 定义链表节点类
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 合并 k 个升序链表
def mergeKLists(lists):
# 创建一个最小堆
heap = []
# 将所有链表的头节点入堆
for i in range(len(lists)):
if lists[i]:
heapq.heappush(heap, (lists[i].val, i, lists[i]))
# 创建一个虚拟头节点，方便操作
dummy = ListNode()
current = dummy
# 逐个弹出堆中的节点并加入结果链表
while heap:
val, idx, node = heapq.heappop(heap)
current.next = node
current = current.next
if node.next:
heapq.heappush(heap, (node.next.val, idx, node.next))
return dummy.next
# 生成链表的方法（根据输入数据生成链表）
def generate_linked_list(nums):
dummy = ListNode()
current = dummy
for num in nums:
current.next = ListNode(num)
current = current.next
return dummy.next
# 读取输入并进行合并
k = int(input()) # 输入链表的数量
lists = []
for _ in range(k):
nums = list(map(int, input().split())) # 读取每个链表
lists.append(generate_linked_list(nums))
# 合并链表
result = mergeKLists(lists)
# 输出合并后的链表
output = []
while result:
output.append(str(result.val))
result = result.next
print(" ".join(output))
Java 代码实现(方法一)
import java.io.*;
import java.util.*;
// 定义链表节点类
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 Main {
// 合并 k 个有序链表
public static ListNode mergeKLists(ListNode[] lists) {
// 使用优先队列，按节点值升序排序
PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
// 将每个链表的头节点（非空）加入队列
for (ListNode list : lists) {
if (list != null) {
pq.offer(list);
}
}
// 创建虚拟头节点，便于构造结果链表
ListNode dummy = new ListNode(0);
ListNode current = dummy;
// 弹出队列中的最小节点，若该节点有后继，则将后继加入队列
while (!pq.isEmpty()) {
ListNode node = pq.poll();
current.next = node;
current = current.next;
if (node.next != null) {
pq.offer(node.next);
}
}
return dummy.next;
}
public static void main(String[] args) throws IOException {
// 使用 BufferedReader 按行读取输入
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if(line == null || line.trim().isEmpty()){
return;
}
int k = Integer.parseInt(line.trim());
ListNode[] lists = new ListNode[k];
for (int i = 0; i < k; i++) {
String str = br.readLine();
if(str == null || str.trim().isEmpty()){
lists[i] = null;
continue;
}
// 分割当前行中的所有整数
String[] tokens = str.trim().split("\\s+");
ListNode dummy = new ListNode(0);
ListNode current = dummy;
for (String token : tokens) {
int val = Integer.parseInt(token);
current.next = new ListNode(val);
current = current.next;
}
lists[i] = dummy.next;
}
// 调用合并链表函数
ListNode result = mergeKLists(lists);
// 输出合并后的链表节点值，用空格隔开
StringBuilder sb = new StringBuilder();
while (result != null) {
sb.append(result.val).append(" ");
result = result.next;
}
System.out.println(sb.toString().trim());
}
}
C++ 代码实现(方法一)
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
// 定义链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 比较器，用于优先队列（小顶堆）
struct cmp {
bool operator()(ListNode* a, ListNode* b) {
return a->val > b->val; // 值越小优先级越高
}
};
// 合并 k 个有序链表
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
// 将每个链表的头节点（非空）入堆
for (auto node : lists) {
if (node)
pq.push(node);
}
ListNode* dummy = new ListNode(0);
ListNode* current = dummy;
while (!pq.empty()) {
ListNode* node = pq.top();
pq.pop();
current->next = node;
current = current->next;
if (node->next)
pq.push(node->next);
}
ListNode* head = dummy->next;
delete dummy;
return head;
}
int main() {
int k;
string line;
// 读取第一行 k 的值
getline(cin, line);
k = stoi(line);
vector<ListNode*> lists;
// 逐行读取每个链表的数据
for (int i = 0; i < k; i++) {
getline(cin, line);
if(line.empty()){
lists.push_back(nullptr);
continue;
}
istringstream iss(line);
int val;
ListNode* dummy = new ListNode(0);
ListNode* current = dummy;
// 读取当前行的所有整数
while (iss >> val) {
current->next = new ListNode(val);
current = current->next;
}
lists.push_back(dummy->next);
delete dummy;
}
// 合并链表
ListNode* merged = mergeKLists(lists);
// 输出结果
while (merged) {
cout << merged->val;
merged = merged->next;
if(merged) cout << " ";
}
cout << endl;
return 0;
}