So this is a LeetCode problem. The main goal is to Merge Two Sorted Lists, but that's not the problem. I looked up the solution below and I am really confused for two reasons.
I tried to understand it, however, I could not wrap my head around the logic. I print statements to see what's going on under the hood and still confuses me why we do node.next = new ListNode(list1.val); instead of node = new ListNode(list1.val);.
Using node = new ListNode(list1.val); return an empty list and I don't know why
var mergeTwoLists = function (list1, list2) {
const head = new ListNode(0);
let node = head;
while (list1 !== null || list2 !== null) {
if (list2 === null || (list1 !== null && list1.val <= list2.val)) {
node.next = new ListNode(list1.val);
list1 = list1.next;
} else {
node.next = new ListNode(list2.val);
list2 = list2.next;
}
node = node.next;
}
return head.next;
};
Why are we using a dummy head?
To simplify the code in the loop. It can be done without dummy, but then the code would look something like this:
let head = null; // no dummy
let node = head;
while (list1 !== null || list2 !== null) {
if (list2 === null || (list1 !== null && list1.val <= list2.val)) {
if (node == null) { // First time only -- need to assign to head
head = new ListNode(list1.val);
} else { // all other times:
node.next = new ListNode(list1.val);
}
list1 = list1.next;
} else {
if (node == null) { // First time only -- need to assign to head
head = new ListNode(list2.val);
} else { // all other times:
node.next = new ListNode(list2.val);
}
list2 = list2.next;
}
node = node.next;
}
return head; // There's no dummy, so return real head
Note how we must distinguish inside the loop between the case where we don't yet have the head node, and must assign to it, and all other cases. With the introduction of a dummy node, this distinction is not necessary in the loop, and after the loop we can skip over that dummy node to find the real head (head.next).
Why do we assign to the next node instead of current
In order to build a linked list, you need to assign to the next attributes of nodes. If you don't assign to next attributes, but to variables, no list is built. If you just do node = new ListNode((list2.val), you create a node and assign it to a variable, but it doesn't become part of a larger linked list. Worse, when in a next iteration you do this again, you lose reference to the previous node that was created in the previous iteration -- there is no way to find it back.