Merge k Sorted Lists

Description

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

Solution(javascript)

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    var mergeTwoLists = function(l1, l2) {
        let mergedList = new ListNode(0);
        let p = mergedList;

        while(l1 && l2) {
            if(l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        if(l1) p.next = l1;
        if(l2) p.next = l2;

        return mergedList.next;
    };
    
    if(!lists.length) return null;
    if(lists.length === 1) return lists[0];
    lists.push(mergeTwoLists(lists[0], lists[1]));
    lists.splice(0, 2);
    return mergeKLists(lists);
};