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 中使用优先队列成本相对较高, 暂时不考虑。