23.Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Analyze

思路一: 分治算法。可以将合并 k 个排序队列转换为合并 2 个排序队列。

图例解释:

cur
dummyNode -> 1 -> 4 -> 5
comparedCur
2 -> 6
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
let result = lists[0] || null
for (let i = 1; i < lists.length; i++) {
const compareList = lists[i]
result = mergeTwoLists(result, compareList)
}
return result
}
var mergeTwoLists = function(curList, compareList) {
const dummyNode = new ListNode(0)
dummyNode.next = curList
let cur = dummyNode
let comparedCur = compareList
while (cur.next && comparedCur) {
if (cur.next.val > comparedCur.val) {
let nextComparedCur = comparedCur.next
comparedCur.next = cur.next
cur.next = comparedCur
comparedCur = nextComparedCur
}
cur = cur.next
}
if (comparedCur) {
cur.next = comparedCur
}
return dummyNode.next
}

思路二: 优先队列

  • 将数组中的队列加入进优先队列(基于最小堆);
  • 如果当前优先队列不为空:
    • 取出当前优先队列顶部队列元素(最小值), 拼接到输出队列中;
    • 同时在优先队列插入取出的顶部队列元素的下一个值;

由于在 JavaScrit 中没有封装好的优先队列, 在此先进行封装优先队列函数(最小堆)。

var len
/**
* to build min heapify from bottom to top;
* the last subscript's parent subscript is Math.floor((len - 1) / 2)
*/
var buildMinHeapify = function(arr) {
len = arr.length
for (let i = Math.floor((len - 1) / 2); i >= 0; i--) {
siftDown(arr, i)
}
return arr
}
/**
* Insert a value into heap. It's an operation called sift up.
*/
var enqueue = function(arr, value) {
arr.splice(len, 0, value)
len++
siftUp()
}
/**
* to keep min heap, it's an operation called sift up.
*/
var siftUp = function() {
let enqueueValSubscript = len - 1
let parent = Math.floor(enqueueValSubscript / 2)
while (parent > 0 && arr[parent] > arr[enqueueValSubscript]) {
swap(arr, parent, enqueueValSubscript)
enqueueValSubscript = parent
parent = Math.floor(enqueueValSubscript / 2)
}
}
/*
* to pick the smallest or the biggest element from the heap and return it;
* Then t'll swap the endest element with the first element, and then keep the
* heap length reduce one. If so, only do once sift down operation in the first element to keep heapify.
*/
var dequeue = function() {
const maxValue = arr[0]
swap(arr, len - 1, 0)
len--
siftDown(arr, 0)
return maxValue
}
/**
* to keep min heap, it's an operation called sift down.
*/
var siftDown = function(arr, i) {
const left = 2 * i + 1
const right = 2 * i + 2
let minSubscript = i
if (left < len && arr[left] < arr[minSubscript]) {
minSubscript = left
}
if (right < len && arr[right] < arr[minSubscript]) {
minSubscript = right
}
if (minSubscript !== i) {
swap(arr, minSubscript, i)
siftDown(arr, minSubscript)
}
}
// swap two value in arr
var swap = function(arr, pointOne, pointTwo) {
const tmp = arr[pointOne]
arr[pointOne] = arr[pointTwo]
arr[pointTwo] = tmp
}

Test case one:

input: var arr = [5, 2, 7, 3, 1, 8, 4]
8
↙ ↘
3 7
↙ ↘ ↙ ↘
2 1 5 4
buildMinHeapify(arr) // [1, 2, 4, 3, 5, 8, 7]
1 1
↙ ↘ enqueue(arr, 6) ↙ ↘
2 4 ---------------> 2 4
↙ ↘ ↙ ↘ ↙ ↘ ↙ ↘
3 5 8 7 3 5 8 7
6
2
return 1 ↙ ↘
dequeue() 3 4
----------------> ↙ ↘ ↙ ↘
6 5 8 7

在 JavaScript 中使用优先队列成本相对较高, 暂时不考虑。