Variable Update in Javascript

MarkW 0
Viewed 61

I am learning about Linked Lists and was looking at this solution for a problem:

   /**
   * Definition for singly-linked list.
   * function ListNode(val, next) {
   *     this.val = (val===undefined ? 0 : val)
   *     this.next = (next===undefined ? null : next)
   * }
   */
   /**
   * @param {ListNode} list1
   * @param {ListNode} list2
   * @return {ListNode}
   */
   var mergeTwoLists = function(list1, list2) {
      let list = new ListNode();
      let head = list;
      console.log("first", head);
      while (list1 && list2) {
          if (list1.val <= list2.val) {
              list.next = list1;
              console.log("second", head);
              list1 = list1.next;
          } else {
              list.next = list2;
              list2 = list2.next;
          }
          list = list.next;
      }
      console.log("third", head, list);
      return head.next;
   };

There is one thing I can not understand. So, the "head" is set to track the "list". How come in the end the they have different values?

linked-list variables javascript
3 Answers

At first, "head" store the first node address. As "list" move along the linked list by passing different node address to "list", the result is they are different at the end. The "head" or "list" are just an address container, so they are not expected to be the same all the time. If they store the same address, they the same.

Kaigagi0 
let head = list;

In the above statement, the variable head holds the current value of the list and is not the reference to the list.

while (list1 && list2) {
      if (list1.val <= list2.val) {
          list.next = list1;
          console.log("second", head);
          list1 = list1.next;
      } else {
          list.next = list2;
          list2 = list2.next;
      }
      list = list.next;
  }

In the above loop, on every iteration the value of the list changes, it will not impact the value of the head.

So, in the end, since head holds the initial address it prints the entire list of values, and list prints the current value of the list (the last node).

See above image enter image description here

here head -> [5, 7, 2, 15] list -> [15]

krishna chaitanya0

So, the "head" is set to track the "list". How come in the end the they have different values?

The reason is that head never is assigned anything else after its first initialisation, while list is assigned something else in the loop. list initially is referencing the same (dummy) node as head, but then later starts referencing different nodes by doing list = list.next repeatedly.

It may help to visualise this. Let's say we merge two lists with values 1, 4 and 2, 3 respectively:

First we have the initialisation happening. Just before the loop starts, we have this siutation:

head list
  ↓   ↓
┌───────────┐
│ val:  0   │
│ next:null │
└───────────┘

list1
  ↓
┌───────────┐   ┌───────────┐
│ val:  1   │   │ val:  4   │
│ next: ──────► │ next:null │
└───────────┘   └───────────┘

┌───────────┐   ┌───────────┐
│ val:  2   │   │ val:  3   │
│ next: ──────► │ next:null │
└───────────┘   └───────────┘
  ↑
list2

In the first iteration of the loop, the first if condition is true, and so list.next = list1 gets executed. This leads to the following:

head list
  ↓   ↓
┌───────────┐
│ val:  0   │
│ next: ─┐  │
└────────│──┘
         │
list1    │ 
  ↓      ▼
┌───────────┐   ┌───────────┐
│ val:  1   │   │ val:  4   │
│ next: ──────► │ next:null │
└───────────┘   └───────────┘

┌───────────┐   ┌───────────┐
│ val:  2   │   │ val:  3   │
│ next: ──────► │ next:null │
└───────────┘   └───────────┘
  ↑
list2

The next statement assigns a different node reference to list1 with list1 = list1.next:

head list
  ↓   ↓
┌───────────┐
│ val:  0   │
│ next: ─┐  │
└────────│──┘
         │
         │      list1
         ▼        ↓
┌───────────┐   ┌───────────┐
│ val:  1   │   │ val:  4   │
│ next: ──────► │ next:null │
└───────────┘   └───────────┘

┌───────────┐   ┌───────────┐
│ val:  2   │   │ val:  3   │
│ next: ──────► │ next:null │
└───────────┘   └───────────┘
  ↑
list2

The last statement in the first iteration of the loop, moves the list reference, with list = list.next, which means head and list no longer reference the same node; and they will never be the same reference again:

head
  ↓
┌───────────┐
│ val:  0   │
│ next: ─┐  │
└────────│──┘
         │
list     │      list1
  ↓      ▼        ↓
┌───────────┐   ┌───────────┐
│ val:  1   │   │ val:  4   │
│ next: ──────► │ next:null │
└───────────┘   └───────────┘

┌───────────┐   ┌───────────┐
│ val:  2   │   │ val:  3   │
│ next: ──────► │ next:null │
└───────────┘   └───────────┘
  ↑
list2

In the second iteration of the loop, we get into the else block, and there we set list.next = list2:

head
  ↓
┌───────────┐
│ val:  0   │
│ next: ─┐  │
└────────│──┘
         │
list     │      list1
  ↓      ▼        ↓
┌───────────┐   ┌───────────┐
│ val:  1   │   │ val:  4   │
│ next: ─┐  │   │ next:null │
└────────│──┘   └───────────┘
         ▼
┌───────────┐   ┌───────────┐
│ val:  2   │   │ val:  3   │
│ next: ──────► │ next:null │
└───────────┘   └───────────┘
  ↑
list2

Then list1 = list1.next will lead to:

head
  ↓
┌───────────┐
│ val:  0   │
│ next: ─┐  │
└────────│──┘
         │
list     │      list1
  ↓      ▼        ↓
┌───────────┐   ┌───────────┐
│ val:  1   │   │ val:  4   │
│ next: ─┐  │   │ next:null │
└────────│──┘   └───────────┘
         ▼
┌───────────┐   ┌───────────┐
│ val:  2   │   │ val:  3   │
│ next: ──────► │ next:null │
└───────────┘   └───────────┘
                  ↑
                 list2

And again, the final statement of this second iteration, will move list:

head
  ↓
┌───────────┐
│ val:  0   │
│ next: ─┐  │
└────────│──┘
         │
         │      list1
         ▼        ↓
┌───────────┐   ┌───────────┐
│ val:  1   │   │ val:  4   │
│ next: ─┐  │   │ next:null │
└────────│──┘   └───────────┘
         ▼
┌───────────┐   ┌───────────┐
│ val:  2   │   │ val:  3   │
│ next: ──────► │ next:null │
└───────────┘   └───────────┘
  ↑               ↑
list            list2

And so the process continues,... Never is head moving, but list is. When the loop exits, the situation will be this:

head
  ↓
┌───────────┐
│ val:  0   │
│ next: ─┐  │
└────────│──┘
         │
         │                 list1 == null
         ▼
┌───────────┐   ┌───────────┐
│ val:  1   │   │ val:  4   │
│ next: ─┐  │   │ next:null │
└────────│──┘   └───────────┘
         ▼                ▲
┌───────────┐   ┌─────────│─┐
│ val:  2   │   │ val:  3 │ │
│ next: ──────► │ next: ──┘ │
└───────────┘   └───────────┘
                  ↑        
                list       list2 == null

The return value is head.next, which indeed is the reference to the first node (with value 1) of the merged list.

I hope this clarified it.

trincot0
Related