此时所有待比较的节点都来到了数组中，和第一步的逻辑一样，只需要遍历一遍数组就可以找到最小的节点，找到后尾插到rhead指向的链表。如下图，其中黄色节点是已排好序的节点，蓝色节点是待比较的节点。
总体逻辑就是这样，接下来循环执行第二步，找到次小的进行尾插，直到数组中的所有节点都为空，此时说明数组中的所有链表都已经排好序了，返回rhead即可。总的过程动图如下：
🐼代码实现：
class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode* rhead = nullptr;//定义合并后链表的头节点 ListNode* rtail = nullptr;//定义合并后链表的尾结点 while (true) { int minIndex = -1;//定义lists数组中最小节点下标，最初等于-1，（下简称最小位置） int i = lists.size();// while (i--) { if (lists[i] != nullptr)//首先判断数组当前位置的节点是否为空 { //当前节点不为空再进来 if (minIndex == -1)//判断最小位置是否是-1，如果是就直接把当前位置赋值给minIndex { minIndex = i; } else if (lists[i]->val < lists[minIndex]->val)//如果minIndex不为-1，则用数组当前位置节点的val与记录的最小位置上节点的val进行比较 { minIndex = i;//如果当前节点的val值更小，那就更新minIndex } } } if (minIndex == -1)//遍历完一遍数组如果minIndex的值还是-1，说明当前数组中的所有节点全是空 { return rhead;//此时说明所有链表已经合并完成，可以返回头节点 } if (rhead == nullptr)//确定新链表的头节点 { rhead = rtail = lists[minIndex]; } else//之后每找出一个最小的节点，进行尾插即可 { rtail->next = lists[minIndex]; rtail = rtail->next; } lists[minIndex] = lists[minIndex]->next;//最小的节点已经尾插到新链表，因此要对最小位置上的节点更新 } } };
上面代码中需要注意的有：minIndex 是用来记录lists中最小节点的位置，它的初始值必须是-1，不能是0或其他数字，因为我们不知道0或其他位置上的节点是否为空。还有需要注意的地方是，每当遍历到一个节点，首先要判断是否为nullptr，当不为空的时候再进行比较，避免出现空指针问题，其次要判断minIndex当前是否为-1，如果是-1，就不用比较，直接把当前位置赋值给minIndex 即可，因为如果当minIndex == -1 的时候进行比较，会导致数组越界。
🐻❄️思路二：分治归并法
分治即“分而治之”，“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的问题，子问题继续按照这样划分，直到问题可以被轻易解决；“治”指的是将子问题单独进行处理。经过分治后的子问题，需要将解进行合并，也就是所谓的“归并”，这样才能得到原问题的解，因此整个分支过程经常采用递归来实现。
针对这道题目来说，我们比较熟悉的是合并两个有序链表，因此我们就可以把合并K个有序链表的问题，划分成合并两个有序链表的问题，具体过程我通过动图来给大家演示，其中相同的颜色代表一个子问题
通过上面的动图我们可以发现，当子问题被分解到只剩一个链表的时候，就无法再进行分解，此时就需要返回了，其实这就是递归的终止条件，也就是当left == right的时候就只剩一个链表，此时就应该返回了，返回的结果就是这一个链表。等左右区间各返回一个链表，此时就要开始对这两个链表进行合并，从而得到一个新的有序链表，再把这个链表作为子问题的处理结果进行返回。这其实很像二叉树的后序遍历，如此循环往复，直到最终的大问题被解决。
🐼代码实现：
class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { return dividemerge(lists, 0, lists.size() - 1); } private: ListNode* dividemerge(vector<ListNode*>& lists, int left, int right) { if (left > right) { return nullptr; } else if (left == right) { return lists[left]; } int mid = left + (right - left) / 2; //分治 ListNode* head1 = dividemerge(lists, left, mid); ListNode* head2 = dividemerge(lists, mid + 1, right); //对子问题处理 return Merge(head1, head2); } private: ListNode* Merge(ListNode* pHead1, ListNode* pHead2)//合并两个有序链表 { if (pHead1 == nullptr) { return pHead2; } if (pHead2 == nullptr) { return pHead1; } ListNode* pHeadret, * tail; if (pHead1->val < pHead2->val) { pHeadret = tail = pHead1; pHead1 = pHead1->next; } else { pHeadret = tail = pHead2; pHead2 = pHead2->next; } while (pHead1 != nullptr && pHead2 != nullptr) { if (pHead1->val < pHead2->val) { tail->next = pHead1; pHead1 = pHead1->next; } else { tail->next = pHead2; pHead2 = pHead2->next; } tail = tail->next; } if (pHead2 != nullptr) { tail->next = pHead2; } if (pHead1 != nullptr) { tail->next = pHead1; } return pHeadret; } };
分治的大思想，其实就体现在下面三行代码中：
//分治 ListNode* head1 = dividemerge(lists, left, mid); ListNode* head2 = dividemerge(lists, mid + 1, right); //对子问题处理 return Merge(head1, head2);
我们只需要知道，前两行代码将一个大问题进行分解，得到的两个子问题，并且经过dividemerge函数把这两个子问题都处理好了，并且得到了两个结果，针对本题，就是得到了两个有序的链表，分别是head1和head2，然后我们只需要对这两个链表进行合并就可以完成题目的要求，也就是第三行代码实现的功能。这就是分治的思想
今天的分享到这里就结束啦，原题链接放在这里，感兴趣的小伙伴可以自己去试试。以上的内容如果对你有帮助的话，可以动动小手点赞、评论、收藏哟，您的支持就是我前进路上最大的动力❤️🥰！
