23_合并K个升序链表
【问题描述】
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
【算法设计思想】
使用优先队列（最小堆）
设计思想：
- 初始化优先队列：创建一个最小堆（优先队列），将每个链表的第一个节点加入堆中。这里堆中存储的是节点的值以及指向该节点的引用，以便于后续操作。
- 构建结果链表：创建一个虚拟头节点（dummy node），用于简化链表的构建过程。然后进入循环，每次从堆中取出最小的节点（即堆顶元素），将其添加到结果链表中。
- 更新堆：如果从堆中取出的节点有下一个节点（即该节点不是所在链表的最后一个节点），则将下一个节点加入堆中。
- 终止条件：当堆为空时，说明所有链表的节点都已经被处理完毕，此时结果链表构建完成。
- 返回结果：返回虚拟头节点的下一个节点作为合并后的链表的头节点。
这种方法的时间复杂度主要取决于堆的操作，对于k个链表，每个链表平均长度为n的情况，时间复杂度大约为O(nk log k)，因为每次插入或删除堆中的元素的时间复杂度为O(log k)。
顺序合并
设计思想：
- 两两合并：从给定的链表列表中选取两个链表，使用一个辅助函数（如前面提到的
mergeTwoLists）将这两个链表合并成一个新的已排序链表。 - 迭代合并：将新合并的链表与列表中的下一个链表再次进行合并。重复此过程，直到所有链表都被合并成一个链表为止。
- 返回结果：最终返回合并后的链表。
这种方法简单直观，但效率相对较低。对于k个链表，每次合并两个链表的时间复杂度为O(n)，而需要合并k-1次，因此总的时间复杂度为O(nk^2)。这在链表数量较少时可能表现尚可，但在链表数量较多时性能会显著下降。
【算法描述】
C++(优先队列)：
/**
* 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:
// 自定义比较器，用于最小堆
struct Cmp {
bool operator()(ListNode* a, ListNode* b) {
return a->val > b->val; // 返回 true 如果 a 的值大于 b 的值
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
// 创建一个最小堆，使用自定义比较器 Cmp
priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;
// 初始化最小堆，将每个链表的头节点加入堆中
for (int i = 0; i < lists.size(); i++) {
if (lists[i]) { // 检查链表头节点是否非空
heap.push(lists[i]); // 将非空的头节点加入堆中
}
}
// 创建一个虚拟头节点，用于简化操作
ListNode* dummy = new ListNode(0);
ListNode* current = dummy; // 当前指针，用于构建合并后的链表
// 处理最小堆，直到堆为空
while (!heap.empty()) {
ListNode* top = heap.top(); // 取出堆顶元素（最小值节点）
heap.pop(); // 从堆中移除堆顶元素
current->next = top; // 将最小值节点添加到合并后的链表中
current = current->next; // 移动当前指针
// 如果取出的节点有下一个节点，将下一个节点加入堆中
if (top->next) {
heap.push(top->next);
}
}
// 返回合并后的链表的头节点
return dummy->next;
}
};
Java(顺序合并)：
/**
* 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 {
/**
* 合并两个有序链表
* @param a 第一个链表
* @param b 第二个链表
* @return 合并后的链表
*/
public ListNode mergeTwoLists(ListNode a, ListNode b) {
// 如果其中一个链表为空，直接返回另一个链表
if (a == null) {
return b;
}
if (b == null) {
return a;
}
// 创建一个虚拟头节点，方便操作
ListNode dummy = new ListNode(0);
ListNode current = dummy;
// 当两个链表都不为空时，进行比较并合并
ListNode l1 = a;
ListNode l2 = b;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
// 将较小的节点连接到当前节点的下一个位置
current.next = l1;
// 移动当前节点和 l1 指针
current = current.next;
l1 = l1.next;
} else {
// 将较小的节点连接到当前节点的下一个位置
current.next = l2;
// 移动当前节点和 l2 指针
current = current.next;
l2 = l2.next;
}
}
// 如果其中一个链表已经遍历完，将另一个链表的剩余部分连接到当前节点的下一个位置
if (l1 == null) {
current.next = l2;
}
if (l2 == null) {
current.next = l1;
}
// 返回合并后的链表，从虚拟头节点的下一个节点开始
return dummy.next;
}
/**
* 合并多个有序链表
* @param lists 链表数组
* @return 合并后的链表
*/
public ListNode mergeKLists(ListNode[] lists) {
// 如果链表数组为空或长度为0，直接返回null
if (lists == null || lists.length == 0) {
return null;
}
// 初始化结果链表为null
ListNode ans = null;
// 遍历链表数组，依次将每个链表与当前结果链表合并
for (int i = 0; i < lists.length; i++) {
ans = mergeTwoLists(ans, lists[i]);
}
// 返回最终合并后的链表
return ans;
}
}
C(顺序合并):
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
* 合并两个有序链表
* @param a 第一个链表
* @param b 第二个链表
* @return 合并后的链表
*/
struct ListNode* mergeTwoLists(struct ListNode* a, struct ListNode* b) {
// 如果其中一个链表为空，直接返回另一个链表
if (a == NULL) {
return b;
}
if (b == NULL) {
return a;
}
// 创建一个虚拟头节点，方便操作
struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
dummy->val = 0;
dummy->next = NULL;
struct ListNode* current = dummy;
// 当两个链表都不为空时，进行比较并合并
struct ListNode* l1 = a;
struct ListNode* l2 = b;
while (l1 != NULL && l2 != NULL) {
if (l1->val <= l2->val) {
// 将较小的节点连接到当前节点的下一个位置
current->next = l1;
// 移动当前节点和 l1 指针
current = current->next;
l1 = l1->next;
} else {
// 将较小的节点连接到当前节点的下一个位置
current->next = l2;
// 移动当前节点和 l2 指针
current = current->next;
l2 = l2->next;
}
}
// 如果其中一个链表已经遍历完，将另一个链表的剩余部分连接到当前节点的下一个位置
if (l1 == NULL) {
current->next = l2;
}
if (l2 == NULL) {
current->next = l1;
}
// 返回合并后的链表，从虚拟头节点的下一个节点开始
struct ListNode* result = dummy->next;
free(dummy); // 释放虚拟头节点的内存
return result;
}
/**
* 合并多个有序链表
* @param lists 链表数组
* @param listsSize 链表数组的大小
* @return 合并后的链表
*/
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
// 如果链表数组为空或长度为0，直接返回NULL
if (lists == NULL || listsSize == 0) {
return NULL;
}
// 初始化结果链表为NULL
struct ListNode* ans = NULL;
// 遍历链表数组，依次将每个链表与当前结果链表合并
for (int i = 0; i < listsSize; i++) {
ans = mergeTwoLists(ans, lists[i]);
}
return ans;
}
Python(顺序合并)：
# 定义单链表节点类
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
# 合并k个升序链表
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
# 合并两个升序链表的辅助函数
def mergeTwoLists(
list1: Optional[ListNode], list2: Optional[ListNode]
) -> Optional[ListNode]:
# 如果其中一个链表为空，则直接返回另一个链表
if list1 is None:
return list2
if list2 is None:
return list1
# 创建一个虚拟头节点，用于简化链表操作
dummy = ListNode(0)
# 当前节点指针，用于构建新的合并后的链表
current = dummy
# 指向两个输入链表的指针
l1 = list1
l2 = list2
# 遍历两个链表，直到至少有一个遍历结束
while l1 is not None and l2 is not None:
# 将值较小的节点连接到新链表，并移动对应的指针
if l1.val <= l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
# 移动当前节点指针
current = current.next
# 将未遍历完的链表剩余部分连接到新链表
if l1 is None:
current.next = l2
if l2 is None:
current.next = l1
# 返回合并后的新链表的头节点（跳过虚拟头节点）
return dummy.next
# 初始化结果链表为None
ans = None
# 依次将每个链表与当前结果链表合并
for i in range(len(lists)):
ans = mergeTwoLists(ans, lists[i])
# 返回最终合并后的链表
return ans