合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

1
2
3
4
5
6
7
8
9
10

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {

    if (lists.length === 1) return lists[0]

    let result = null
    for (let i = 0; i < lists.length; i++) {
      result = helper(result, lists[i])
    }

    function helper(l1, l2) {
      let res = new ListNode(0, null)
      let temp = res

      while (l1 && l2) {
        if (l1.val <= l2.val) {
          temp.next = l1
          l1 = l1.next
        } else {
          temp.next = l2
          l2 = l2.next
        }
        temp = temp.next
      }

      temp.next = l1 ? l1 : (l2 ? l2 : null)

      return res.next
    };

    return result

};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    if (lists.length === 1) return lists[0]

    function divide(lists, l, r) {
      if (l === r) {
        return lists[l]
      }
      if (l > r) {
        return null
      }

      let mid = (l + r) >> 1

      return merge(divide(lists, l, mid), divide(lists, mid + 1, r))
    }

    function merge(l1, l2) {
      let res = new ListNode(0, null)
      let temp = res

      while (l1 && l2) {
        if (l1.val <= l2.val) {
          temp.next = l1
          l1 = l1.next
        } else {
          temp.next = l2
          l2 = l2.next
        }
        temp = temp.next
      }

      temp.next = l1 ? l1 : (l2 ? l2 : null)

      return res.next
    };

    return divide(lists, 0, lists.length - 1)

};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/merge-k-sorted-lists

← 括号生成两两交换链表中的节点→