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

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

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

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