目录
前言：
今天给大家分享一道面试中常见的题目——合并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就可以实现。修改后的结构如下图所示：
此时所有待比较的节点都来到了数组中，和第一步的逻辑一样，只需要遍历一遍数组就可以找到最小的节点，找到后尾插到rhead指向的链表。如下图，其中黄色节点是已排好序的节点，蓝色节点是待比较的节点。
总体逻辑就是这样，接下来循环执行第二步，找到次小的进行尾插，直到数组中的所有节点都为空，此时说明数组中的所有链表都已经排好序了，返回rhead即可。总的过程动图如下：
