题目
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[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示例 2：
输入：lists = []
输出：[]示例 3：
输入：lists = [[]]
输出：[]提示：
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i]按 升序 排列lists[i].length的总和不超过10^4
解答
- 归并排序(使用单指针)
在mergeTwoLists函数中，使用了一个虚拟头节点，将其next指向合并后的链表头节点，然后不断更新cur指针的值，使其指向合并后的链表的最后一个节点，最后返回虚拟头节点的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* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* temp1 = list1;
ListNode* temp2 = list2;
ListNode* newHead = new ListNode(); // 虚拟头节点
ListNode* cur = newHead;
while (temp1 != NULL && temp2 != NULL) {
if (temp1->val < temp2->val) {
cur->next = temp1;
temp1 = temp1->next;
}
else {
cur->next = temp2;
temp2 = temp2->next;
}
cur = cur->next; // 更新cur指针的值
}
if (temp1 != NULL) {
cur->next = temp1;
}
if (temp2 != NULL) {
cur->next = temp2;
}
return newHead->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* head = nullptr;
for (int i = 0; i < lists.size(); i++) {
head = mergeTwoLists(head, lists[i]);
}
return head;
}
};- 归并排序（使用二级指针实现）
在mergeTwoLists函数中，使用了一个curNode指针指向合并后的链表，使用了一个二级指针temp，根据list1和list2的值大小，让temp指向较小的那个节点，然后将其插入到curNode之后，并更新curNode指向插入后的链表最后一个节点。最后，如果还有剩余节点，将其直接补充到合并后的链表尾部。
/**
* 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* mergeTwoLists(ListNode* list1, ListNode* list2)
{
ListNode* head = nullptr;
ListNode* curNode = nullptr;
ListNode** temp = nullptr;
bool isFirst = true;
while(list1 != nullptr && list2 != nullptr)
{
temp = (list1 -> val < list2 -> val)? &list1:&list2; //使用二级指针，因为temp如果是一级指针，那么temp = temp->next;是无法改变list1和list2的值的，而二级指针可以间接改变list1和list2的地址。
if(isFirst)
{
head = *temp;
curNode = *temp;
isFirst = false;
}
else
{
curNode -> next = *temp;
curNode = curNode -> next;
}
*temp = (*temp) -> next;
}
if(nullptr != list1)
{
if(isFirst) //有一方链表为空
{
head = list1;
}
else //剩下结点直接补齐
{
curNode -> next = list1;
}
}
if(nullptr != list2)
{
if(isFirst)
{
head = list2;
}
else
{
curNode->next = list2;
}
}
return head;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* head = nullptr;
for(int i = 0; i < lists.size(); i++)
{
head = mergeTwoLists(head, lists[i]);
}
return head;
}
};- 使用优先队列
可以将所有的链表的首节点放入一个小根堆中，每次从堆中取出最小节点，将该节点接入最终链表，并将该节点的下一个节点加入堆中。重复该过程直到堆为空。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
//如果传进来的链表为空，直接返回空指针。
if(lists.empty()) {
return nullptr;
}
//定义一个优先队列，该队列将所有链表的头结点按照节点的值从小到大排列。
priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
//定义一个虚拟头结点和一个当前节点cur。
ListNode dummy(0);
ListNode* cur = &dummy;
//将所有链表的头结点加入到优先队列中。
for(auto& node: lists) {
if(node) {
pq.push(node);
}
}
//每次取出队列中的最小值，将该节点加入到合并后的链表中，并将该节点的下一个节点加入到队列中。
while(!pq.empty()) {
auto temp = pq.top();
pq.pop();
cur->next = temp;
cur = cur->next;
if(temp->next) {
pq.push(temp->next);
}
}
//返回合并后的链表。
return dummy.next;
}
private:
//自定义比较函数，用于优先队列。 保证队尾元素最大
struct cmp {
bool operator() (const ListNode* a, const ListNode* b) {
return a->val > b->val;
}
};
};
请注意优先队列的定义方式：
priority_queue<ListNode*, vector<ListNode*>, cmp> pq是一个定义了一个priority_queue对象pq，其中包含三个参数：
ListNode*是存储在堆中的元素的类型，即堆元素的指针类型为ListNode*；vector<ListNode*>是底层容器类型，即使用vector来实现堆；cmp是比较函数，用于堆中元素的排序方式。根据这个定义，我们可以理解
priority_queue的工作原理：它是一个基于堆的数据结构，其中的元素按照指定的比较函数cmp进行排序。priority_queue是一个可以高效获取最大（或最小）元素的容器，因此常常被用来实现一些需要对元素进行优先级处理的算法。