Im confused on how head.next returns the entire list instead of a next value such l1,l2,dummy .next does in the code below. particularly I’m wondering how head.next returns an entire sorted array and skips the -1 value that was input on the second line.
let mergeTwoLists = function (l1, l2) {
let dummy = new ListNode(-1);
let head = dummy;
while (l1 !== null && l2 !== null) {
if (l1.val <= l2.val) {
dummy.next = l1;
l1 = l1.next;
} else {
dummy.next = l2;
l2 = l2.next;
}
dummy = dummy.next;
}
if (l1 !== null) {
dummy.next = l1;
} else {
dummy.next = l2;
}
return head.next;
};
class ListNode {
constructor(val = null, next = null) {
this.val = val;
this.next = next;
}
}
Advertisement
Answer
Maybe it helps when visualising how the list is built:
Let the input be a list with values [3, 9] and another with just [4]:
l1 ↓ 3 → 9 → null l2 ↓ 4 → null
Before the loop starts a new node is created:
head ↓ -1 ↑ dummy
The loop will make its first iteration, and the if condition is true. First dummmy.next is adapted, which leads to this situation:
head l1 ↓ ↓ -1 → 3 → 9 → null ↑ dummy l2 ↓ 4 → null
… and then l1 is reassigned a new reference:
head l1 ↓ ↓ -1 → 3 → 9 → null ↑ dummy l2 ↓ 4 → null
The last statement in the loop assigns a new reference to dummy:
head l1
↓ ↓
-1 → 3 → 9 → null
↑
dummy
l2
↓
4 → null
The loop iterates a second time, and the if condition is now false, so we get in the else block. First dummmy.next is adapted (this breaks the link it had with l1, and so I move the visualisation of l1 and l2):
head l2
↓ ↓
-1 → 3 → 4 → null
↑
dummy
l1
↓
9 → null
… and then l1 is reassigned a new reference, in this case it becomes null:
head l2
↓ ↓
-1 → 3 → 4 → null
↑
dummy
l1
↓
9 → null
The last statement in the loop assigns a new reference to dummy:
head l2
↓ ↓
-1 → 3 → 4 → null
↑
dummy
l1
↓
9 → null
At this stage the loop condition is no longer true (l2 is null), and so the if block that follows the loop is executed. This links dummy.next with the remaining (not null) reference. Again, for sake of the visualisation, I swap the position of l1 and l2:
head l1
↓ ↓
-1 → 3 → 4 → 9 → null
↑
dummy
l2
↓
null
Now we get to the final statement: return head.next. Notice how head did not ever move away from the new node that was created at the start.
So the returned reference is:
head l1
↓ ↓
-1 → 3 → 4 → 9 → null
↑
returned
l2
↓
null
Note how head keeps pointing to the node with -1 during the whole execution of this function. The temporary node with value -1 will be garbage collected, as there is no variable referencing it any more once the function has returned (head is a local variable).