# 17.\[Linked List]: Merge k Sorted Lists

23\. Merge k Sorted ListsHard17.3K624Companies

You are given an array of `k` linked-lists `lists`, each linked-list is sorted in ascending order.

*Merge all the linked-lists into one sorted linked-list and return it.*

**Example 1:**

<pre><code><strong>Input: lists = [[1,4,5],[1,3,4],[2,6]]
</strong><strong>Output: [1,1,2,3,4,4,5,6]
</strong><strong>Explanation: The linked-lists are:
</strong>[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
</code></pre>

**Example 2:**

<pre><code><strong>Input: lists = []
</strong><strong>Output: []
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: lists = [[]]
</strong><strong>Output: []
</strong></code></pre>

**Constraints:**

* `k == lists.length`
* `0 <= k <= 104`
* `0 <= lists[i].length <= 500`
* `-104 <= lists[i][j] <= 104`
* `lists[i]` is sorted in **ascending order**.
* The sum of `lists[i].length` will not exceed `104`.

{% embed url="<https://leetcode.com/problems/merge-k-sorted-lists/>" %}

> time: O(mlogn), m is the max length among lists, n is the length of lists

> space: O(n)

```jsx
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    const minHeap = new Heap([], (a, b) => a[1].val <= b[1].val);
    for (let i = 0; i < lists.length; i++) {
        const node = lists[i];
        if (node !== null) {
            minHeap.insert([i, node]);
        }
    }
    
    const prev = new ListNode(-1, null);
    let currentNode = prev;
    while (minHeap.size !== 0) {
        const [index, minNode] = minHeap.remove();
        currentNode.next = minNode;
        currentNode = currentNode.next;

        lists[index] = lists[index].next;
        if (lists[index] !== null) {
            minHeap.insert([index, lists[index]]);
        }
    }

    return prev.next;
};

class Heap {
    constructor(arr, predicate = (a, b) => a <= b) {
        this.predicate = predicate;
        this.size = arr.length;
        this.heap = this.buildHeap(arr);
    }

    buildHeap(arr) {
        let currentIndex = Math.floor((arr.length - 1 - 1) / 2);
        while (currentIndex >= 0) {
            this.siftDown(arr, currentIndex, arr.length - 1);
            currentIndex--;
        }

        return arr;
    }

    insert(v) {
        this.heap.push(v);
        this.size++;

        this.siftUp(this.heap, this.heap.length - 1);

    }

    remove(v) {
        this.swap(this.heap, 0, this.heap.length - 1);
        const elementToRemove = this.heap.pop();
        this.size--;
        
        this.siftDown(this.heap, 0, this.heap.length - 1);
        return elementToRemove;
    }

    siftUp(heap, currentIndex) {
        let parentIndex = Math.floor((currentIndex - 1) / 2);
        while (parentIndex >= 0) {
            if (this.predicate(heap[parentIndex], heap[currentIndex])) {
                break;
            }

            this.swap(heap, parentIndex, currentIndex);
            currentIndex = parentIndex;
            parentIndex = Math.floor((currentIndex - 1) / 2);
        }
        return heap;
    }

    siftDown(heap, currentIndex, endIndex) {
        let left = currentIndex * 2 + 1;

        while (left <= endIndex) {
            let min = left;
            const right = currentIndex * 2 + 2;
            if (heap[right] !== undefined && this.predicate(heap[right], heap[min])) {
                min = right;
            }

            if (this.predicate(heap[currentIndex], heap[min])) break;
            this.swap(heap, currentIndex, min);
            currentIndex = min;
            left = currentIndex * 2 + 1;
        }

        return heap;
    }

    clear() {
        this.heap = [];
        this.size = 0;
    }

    swap(arr, a, b) {
        [arr[b], arr[a]] = [arr[a], arr[b]];
    }

}
```