CODEWITHSUNDEEP
javascript
Yujin Dong
Yujin Dong

Reputation: 483

Why this ListNode uses dummy head and assign value to the next node instead of current one?

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.

  1. Why are we using a dummy head?
  2. Why do we assign to the next node instead of current

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;
};

Upvotes: 1

Views: 293

Answers (1)

trincot
trincot

Reputation: 350310

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.

Upvotes: 1

Related Questions