题目：合并K个排序链表
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists/
解题思路
相比合并两个有序链表题目条件由双链表合并变成多链表合并，而在面对这种多维最简单就是使用暴力法解决(代码实现会贴出暴力法代码)，相比暴力法我更喜欢另一种解法：分治法，那么如何去分治，先不急，举个🌰，求1+2+3.....+97+99+100，我们都知道最佳的解法是(1+100)+(2+99)+(3+98).....，这种解法相当于把100个数值相加化解成50个一样的数值相加，那么分治法一定程度上就是参考这种解法：
- 我们可以从数组和头和尾开始对数组进行两两合并，定义位置
L=0和R=lists.length-1
合并完成后L向右移R向左移
- 当
L大于等于R时意味着第一轮合并已经完成，如下图：
这个时候要合并的长度从len变成len/2,那么继续循环上面的步骤，就会变成len/4,len/8....,当R=0时，就是合并的最终结果
代码实现
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
let mergeKLists = (lists) => {
if (!lists || !lists.length) return null;
let left = 0,
right = lists.length;
while (right) {
while (left < right) {
lists[left] = merge(lists[left], lists[right]);
left++;
right--;
}
left = 0;
}
return lists[0]
};
let merge = (list1, list2) => {
let dummyHead = new ListNode(0);
let cur = dummyHead;
while (list1 && list2) {
if (list1.val < list2.val) {
cur.next = list1;
list1 = list1.next
} else {
cur.next = list2;
list2 = list2.next
}
cur = cur.next
}
if (list1) cur.next = list1;
if (list2) cur.next = list2;
return dummyHead.next
}