LeetCode - 23. Merge k Sorted Lists algo issue

I was trying to solve this LeetCode Problem, and have been failing at it.

The problem

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:

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

Example 2:

Input: lists = [] Output: []

Example 3:

Input: lists = [[]] Output: []

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.

My Algorithm:

• Variables with purpose:
  • head: Holds reference of head element.
  • temp: Holds reference of current pointing element and gets updated to point to next in list.
  • min: Holds minimum value of current elements
  • index: Holds index of list which has minimum value.
• Loop while min is smaller than Number.MAX_SAFE_INTEGER
• Start of loop, set min to max
• Loop on every list:
  • Check if val < min
    • If so, update min with val
    • Set index to i
  • Check if node exists at that index
    • If so, set reference of node to temp.next
    • Point to node.next
    • Reset index so we do not get stale node.
• At the end of loop, return head

Also attaching sample code:

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    let head = null;
    let temp = null;
    let min: number;
    let index: number;
    function setVal(node): void {
        if (temp === null) temp = node;
        else temp.next = node;
        if (!head) head = temp;
        if (node) temp = temp.next;
    }
    do {
        // Used only for debug purpose
        const map = [];
        min = Number.MAX_SAFE_INTEGER;
        for (let i = 0; i< lists.length; i++) {
            map.push(lists[i] && lists[i].val)
            if (getVal(lists[i]) < min) {
                min = lists[i].val;
                index = i;
            }
        }
        if (lists[index]) {
            setVal(lists[index]);
            lists[index] = lists[index].next;
            index = null;
        }
        console.log(min, map)
    } while (min < Number.MAX_SAFE_INTEGER)
    return head;
};

function getVal(node): number {
    return node && node.val != null ? node.val : Number.MAX_SAFE_INTEGER
}

Following is the input:

lists = [[1,4,5],[1,3,4],[2,6]]

I'm seeing the output as:

1 [ 1, 1, 2 ]
1 [ 4, 1, 2 ]
2 [ 4, 3, 2 ]
3 [ 4, 3, 6 ]
4 [ 4, 4, 6 ]
1 [ 1, 4, 6 ] <--- Error point
2 [ 2, 4, 6 ]
3 [ 3, 4, 6 ]

As you can see, on 6th iteration I'm again getting 1 but I'm not able to understand where that reference is coming from.

Note: I'm not looking for solution but help in correcting my algorithm. I'm sure there are better ways to solve but this is what I could think of, so would like to progress from this point.

The problem lies in your setVal function. If you step through your code in a debugger, you will notice that after the first iteration of your loop temp points to the second node of your first list.

Ie because you do

temp = node;
temp = temp.next;

in the first call of setVal.

Then in the second iteration you will do

temp.next = node

This will make the head of the second list to be the successor of the second element in the first list (and the third element of the first list to be lost).

Thus after a while, when the second element of the first list is handled as the new minimum, you are advancing to its successor, which is not the orginal value of 5 but the value of 1 from the second list. This is (at least with this speicific input) creating an endless loop.

Not sure what your thoughts were behind this implementation of setVal, so I'm not gonna fix it for you, but the remarks above should point you in the right direction so you can fix your algorithm.

UPDATE

And even if you managed to fix your implementation by now, it still seems a bit unstructured and clumsy, so I'd like to provide a (IMHO) cleaner implementation of your approach

function mergeKLists(lists) {
    let 
      head = null, //head (ie first element) of the resulting list
      tail = null, //tail (ie last element) of the resulting list
      min = null; //index of the minimum in lists
    do {
        min = null;
        // search for the minimum head in the input lists
        for (let i = 0; i < lists.length; i++) {
            if (lists[i] && (min === null || lists[i].val < lists[min].val)) {
                min = i;
            }
        }

        if (min !== null) {
            let tmp = lists[min];  //store the found minimum in a temp variable
            lists[min] = lists[min].next;  //advance to the next node in the list where you found the minimum
            if (!head) {  //if there is no head (and tail) yet
                head = tail = tmp;  //the found minimum is head and tail of the result
            } else {  //if there is already a head (and a tail)
                tail.next = tmp; //attach the minimum node to the list (ie it's the next of the current tail)
                tail = tmp;  //and make it the new tail
            }
            tail.next = null; // clear an existing successor of the result's tail
        }
    } while (min !== null)
    return head;
};


let result = mergeKLists([
    { val: 1, next: { val: 4, next: { val: 5, next: null } } },
    { val: 1, next: { val: 3, next: { val: 4, next: null } } },
    { val: 2, next: { val: 6, next: null } }
])

//iterate over the result and print the value
while (result) {
    console.log(result.val);
    result = result.next;
}