### 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

curdummyNode -> 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}

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

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 arrvar 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