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?
CodePudding user response：
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.
CodePudding user response：
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
here head -> [5, 7, 2, 15] list -> [15]
CodePudding user response：
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.