前言：

 今天给大家分享一道面试中常见的题目——合并K个升序链表，我会用暴力和分治两钟方法去求解这道题目，通过动图展示问题求解的全过程。这里提醒大家，画图是我们求解复杂问题的有效手段，有时可以起到事半功倍的效果，各位小伙伴在做题的过程中如果遇到麻烦，不妨动手画画图哟。

🐻题目描述：

 合并K个升序的链表并将结果作为一个升序的链表返回其头节点。例如：

• 输入：[{1,2},{1,4,5},{6},{2,3,5}]
• 输出：{1,1,2,2,3,4,5,5,6}

🐻‍❄️思路一：暴力求解法

 首先根据题目的描述，画出如下模拟图。

🐼第一步：确定合并后链表的头节点rhead

 从上图中可以看出：lists中存放是每个链表的头节点，那合并后链表的头节点一定是这四个头结点中最小的那个，因此我们只需要遍历lists就可以找到最小的头节点，然后把它赋值给rhead，执行完第一步得到的结果如下图，用黄色标注已经排好序的节点：

🐼第二步：选择次小的进行尾插

如上图，接下来我们需要在所有蓝色节点中选出最小的一个尾插到rhead指向的链表，因此我们再定义一个rtail指向合并后链表的最后一个节点。但是我们发现如果按照上图的结构，直接从四个蓝色节点里面选出最小的，显然十分困难， 因为第一个链表中待比较的节点不再数组中。如果向第一步那样，所有的节点都在数组中，那选出最小的节点简直是易如反掌，只需要遍历一遍数组即可。因为lists数组中存的永远都是头节点，所以这里我们直接修改第一个链表的头节点即可，通过lists[0] = lists[0]->next就可以实现。修改后的结构如下图所示：