23 合并K个排序链表（c++）解析

在解决「合并K个排序链表」这个问题之前，我们先来看一个更简单的问题:

如何合并两个有序链表?

假设链表a和b的长度都是 n，如何在 O(n)的时间代价以及 O(1)的空间代价完成合并?

这个问题在面试中常常出现，为了达到空间代价是 O(1)，我们的宗旨是「原地调整链表元素的next 指针完成合并」。

首先我们需要一个变量 head 来保存合并之后链表的头部，你可以把 head 设置为一个虚拟的头(也就是head 的 val属性不保存任何值)，这是为了方便代码的书写，在整个链表合并完之后，返回它的下一位置即可。我们需要一个指针 tail 来记录下一个插入位置的前一个位置，以及两个指针 aPtr和 bPtr 来记录 a和b未能合并部分的第一位。注意这里的描述，tail不是下一个插入的位置，aPtr和 bPtr所指向的元素处于「待合并」的状态，也就是说它们还没有合并入最终的链表。当然你也可以给他们赋予其他的定义，但是定义不同实现就会不同。

当 aPtr 和 bPtr 都不为空的时候，取 val 属性较小的合并;
如果 aPtr为空，则把整个 bPtr 以及后面的元素全部合并;
bPtr 为空时同理。

在合并的时候，应该先调整 tail的 next 属性，再后移tail和*Ptr(aPtr 或者 bPtr)。

那么这里 tail 和*Ptr是否存在先后顺序呢?

它们谁先动谁后动都是一样的，不会改变任何元素的 next 指针。

ListNode* mergeTwoLists(ListNode *a, ListNode *b) {if ((!a) || (!b)) return a ? a : b;     // 如果其中一个输入链表为空，则直接返回另一个链表 如果 a 不为空，则返回 a，否则返回 b//ListNode head 声明了一个名为 head 的局部变量，类型为 ListNode。在这个声明中，head 并不是一个指针，而是一个对象或者说是一个节点。//一个指针 `tail`，将其指向 `head` 指针所指向的地址ListNode head, *tail = &head, *aPtr = a, *bPtr = b; // 初始化一个虚拟头结点和一个尾指针 定义用于遍历输入链表的指针while (aPtr && bPtr) {if (aPtr->val < bPtr->val) {tail->next = aPtr; aPtr = aPtr->next; // 如果链表 'a' 的值较小，则将其追加到合并后的链表中  aPtr移动到链表 'a' 的下一个节点} else {tail->next = bPtr; bPtr = bPtr->next;}tail = tail->next;//将尾指针移动到合并后的链表的最后一个节点}tail->next = (aPtr ? aPtr : bPtr); // 将剩余的节点（如果有）追加到合并后的链表中return head.next;// 返回合并后的链表的起始节点（不包括虚拟头结点）
}

复杂度分析
时间复杂度:O(n)。
空间复杂度:O(1)。

1.1 暴力求解

暴力解法就不演示了，自己可以尝试一下

1.2 逐一比较

不如直接看1.3优先队列解法

1.3 优先队列

对于优先队列有这几种做法:

方法1:建立优先队列(最大堆或者最小堆均可)，全部元素接连入队; 最后再不断弹出，构建链表。这也是一种想法，不过这样子效率就有些低下了。
方法2： 依然建立优先队列，不过不需要全部元素一次性入队；只需要让链表头元素入队即可，弹出该元素后，该链表往后移。

使用小根堆（优先队列）合并 K 个有序链表

class Solution {
public:// 小根堆的回调函数struct cmp{ //定义了一个函数对象bool operator()(ListNode *a,ListNode *b){//重载了小根堆的比较操作符,用于比较两个节点的值return a->val > b->val;//大的值先被放入尾部，自然小的值就会在顶部}};ListNode* mergeKLists(vector<ListNode*>& lists) {//存储元素类型，整体类型，以及小根堆定义priority_queue<ListNode*, vector<ListNode*>, cmp> pri_queue;// 建立大小为k的小根堆,声明了一个优先队列 pri_queue，它存储的元素类型是 ListNode*，表示指向链表节点的指针。//重载了小根堆的比较操作符的目的是为了定义优先队列中节点的比较规则，默认情况下，优先队列使用的是 < 操作符进行比较，即比较节点指针的大小；但在这个场景下，我们需要根据节点的值来进行比较，而不是比较节点指针的大小//使用了上面定义的 cmp 函数对象来比较节点的值。这样定义的效果是，队首元素是值最小的节点。for(auto elem : lists){if(elem) pri_queue.push(elem);//将所有非空的链表头节点（elem）依次加入小根堆}// 可以使用哑节点/哨兵节点ListNode dummy(-1);ListNode* p = &dummy;//这个哑节点用于简化链表的操作，我们将通过 p 指针来不断连接合并后的链表// 开始出队while(!pri_queue.empty()){ListNode* top = pri_queue.top(); pri_queue.pop();p->next = top; p = p->next;//每次取出堆顶元素（值最小的节点）if(top->next) pri_queue.push(top->next);//被取出的下一个节点入队}return dummy.next;  }
};

1.4 逐一合并

代码如下：

class Solution {
public:ListNode* mergeTwoLists(ListNode *a, ListNode *b) {if ((!a) || (!b)) return a ? a : b; //检查 `a` 和 `b` 是否为空，如果其中一个为空，直接返回另一个链表ListNode head, *tail = &head, *aPtr = a, *bPtr = b;//它采用了迭代的方法，使用了三个指针 `tail`、`aPtr` 和 `bPtr`，以及一个虚拟头结点 `head`while (aPtr && bPtr) {if (aPtr->val < bPtr->val) {tail->next = aPtr; aPtr = aPtr->next;} else {tail->next = bPtr; bPtr = bPtr->next;}tail = tail->next;}tail->next = (aPtr ? aPtr : bPtr);return head.next;}ListNode* mergeKLists(vector<ListNode*>& lists) { //函数用于合并给定的 K 个有序链表，存储在 `lists` 向量中ListNode *ans = nullptr;//size_t 是 C++ 中的一种无符号整数类型，通常用于表示数组索引、大小和长度等非负整数值for (size_t i = 0; i < lists.size(); ++i) {ans = mergeTwoLists(ans, lists[i]);//通过多次调用 `mergeTwoLists` 函数来逐个合并链表，最终得到一个合并后的链表。}return ans;}
};

1.5 分治

class Solution{
public:ListNode* mergeTwoLists(ListNode*a, ListNode*b){if((!a)||(!b)) return a? a: b;ListNode head, *tail =&head, *aPtr = a, *bPtr = b;      while(aPtr && bPtr){if(aPtr->val<bPtr->val){tail->next = aPtr; aPtr = aPtr ->next;}else if(aPtr->val>= bPtr->val){tail ->next = bPtr; bPtr = bPtr ->next;}tail = tail->next;}if((!aPtr)||(!bPtr)){tail->next = (aPtr?aPtr:bPtr);}return head.next;}//l 和 r 表示当前要处理的链表范围的左右边界。ListNode* merge(vector<ListNode*> &lists, int l ,int r){if(l == r) return lists[l];//如果左右边界相等，说明只有一个链表需要处理，直接返回该链表的头节点。if(l>r) return nullptr;//如果左边界大于右边界,则返回空指针int mid = (l+r)>>1;//二进制数进行右移操作，相当于除以2 return mergeTwoLists(merge(Lists, l, mid), merge(lists, mid+1,r));//递归地将左右两个子范围的链表进行合并，递归到最后比如当1=mid 或者mid+1=r时直接返回lists}ListNode* mergeKLists(vector<ListNode*> &lists){return merge(lists, 0, lists.size()-1);}};