5.merge-k-sorted-lists.md

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

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
    normalize(lists);
    var head = new ListNode();
    var taill = head;

    while (lists.length) {
        let min = lists[0].val;
        let minINdex = 0;

        for (let i = 0; i < lists.length; ++i) {
            if (lists[i].val < min) {
                min = lists[i].val;
                minINdex = i;
            }
        }
        taill.next = new ListNode(min);
        taill = taill.next;
        if (lists[minINdex].next === null) {
            lists.splice(minINdex, 1);
        } else {
            lists[minINdex] = lists[minINdex].next;
        }

    }

    return head.next;

};

function normalize(lists) {
    for (var i = 0; i < lists.length; ++i) {
        if (lists[i] === null) {
            lists.splice(i, 1);
            --i;
        }
    }
}