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

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

简单思路

  1. 实现合并两个升序链表的方法，将 lists 迭代得出结果
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
var mergeKLists = function (lists) {
  const mergeTwoList = (link1, link2) => {
    const dummyHead = new ListNode()
    let cur = dummyHead
    while (link1 && link2) {
      if (link1.val < link2.val) {
        cur.next = link1
        link1 = link1.next
      } else {
        cur.next = link2
        link2 = link2.next
      }
      cur = cur.next
    }
    if (link1) {
      cur.next = link1
    }
    if (link2) {
      cur.next = link2
    }
    return dummyHead.next
  }
  let curLink = null
  for (const link of lists) {
    curLink = mergeTwoList(link, curLink)
  }
  return curLink
}

改进思路

  1. 迭代合并方法简单但效率一般，时间复杂度为 O(k * k * n)，n 为链表平均长度
  2. 考虑维护一个最小堆，将时间复杂度降低到 O(k * n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var mergeKLists = function (lists) {
  let heap = new BinaryHeap(function (node) {
    return node.val
  })

  for (let i = 0; i < lists.length; ++i) {
    let node = lists[i]
    if (node !== null) {
      heap.push(node)
    }
  }

  let dummyHead = new ListNode()
  let cur = dummyHead
  while (heap.size() > 0) {
    let node = heap.pop()
    if (node.next !== null) {
      heap.push(node.next)
    }
    cur.next = node
    cur = cur.next
  }
  return dummyHead.next
}
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
function BinaryHeap(scoreFunction) {
  this.content = []
  this.scoreFunction = scoreFunction
}

BinaryHeap.prototype = {
  push: function (element) {
    // Add the new element to the end of the array.
    this.content.push(element)
    // Allow it to bubble up.
    this.bubbleUp(this.content.length - 1)
  },

  pop: function () {
    // Store the first element so we can return it later.
    var result = this.content[0]
    // Get the element at the end of the array.
    var end = this.content.pop()
    // If there are any elements left, put the end element at the
    // start, and let it sink down.
    if (this.content.length > 0) {
      this.content[0] = end
      this.sinkDown(0)
    }
    return result
  },

  remove: function (node) {
    var length = this.content.length
    // To remove a value, we must search through the array to find
    // it.
    for (var i = 0; i < length; i++) {
      if (this.content[i] != node) continue
      // When it is found, the process seen in 'pop' is repeated
      // to fill up the hole.
      var end = this.content.pop()
      // If the element we popped was the one we needed to remove,
      // we're done.
      if (i == length - 1) break
      // Otherwise, we replace the removed element with the popped
      // one, and allow it to float up or sink down as appropriate.
      this.content[i] = end
      this.bubbleUp(i)
      this.sinkDown(i)
      break
    }
  },

  size: function () {
    return this.content.length
  },

  bubbleUp: function (n) {
    // Fetch the element that has to be moved.
    var element = this.content[n],
      score = this.scoreFunction(element)
    // When at 0, an element can not go up any further.
    while (n > 0) {
      // Compute the parent element's index, and fetch it.
      var parentN = Math.floor((n + 1) / 2) - 1,
        parent = this.content[parentN]
      // If the parent has a lesser score, things are in order and we
      // are done.
      if (score >= this.scoreFunction(parent)) break

      // Otherwise, swap the parent with the current element and
      // continue.
      this.content[parentN] = element
      this.content[n] = parent
      n = parentN
    }
  },

  sinkDown: function (n) {
    // Look up the target element and its score.
    var length = this.content.length,
      element = this.content[n],
      elemScore = this.scoreFunction(element)

    while (true) {
      // Compute the indices of the child elements.
      var child2N = (n + 1) * 2,
        child1N = child2N - 1
      // This is used to store the new position of the element,
      // if any.
      var swap = null
      // If the first child exists (is inside the array)...
      if (child1N < length) {
        // Look it up and compute its score.
        var child1 = this.content[child1N],
          child1Score = this.scoreFunction(child1)
        // If the score is less than our element's, we need to swap.
        if (child1Score < elemScore) swap = child1N
      }
      // Do the same checks for the other child.
      if (child2N < length) {
        var child2 = this.content[child2N],
          child2Score = this.scoreFunction(child2)
        if (child2Score < (swap == null ? elemScore : child1Score)) swap = child2N
      }

      // No need to swap further, we are done.
      if (swap == null) break

      // Otherwise, swap and continue.
      this.content[n] = this.content[swap]
      this.content[swap] = element
      n = swap
    }
  },
}