0
87
ViewsJavaScript Linked List Confusion
I was doing some leet code and I have gotten really confused by how the linked list is being traversed and created.
Can someone please shed some light with regards to the question below
/**
* 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) {
var list1_head = list1;
let temp = new ListNode(0);
let head = temp;
console.log(head);
if(list1 && list2){
while(list1 && list2){
if(list1.val < list2.val){
temp.next = list1;
list1 = list1.next;
}
else{
temp.next = list2;
list2 = list2.next;
}
console.log('First Temp');
temp = temp.next;
console.log(temp);
}
}
if(list1){
temp.next = list1;
}
else if (list2){
temp.next = list2;
}
console.log('--temp--');
console.log(temp);
console.log("Why isn't the value of temp 1 as set above");
console.log('--head--');
console.log(head);
return head.next;
};
My question is why didn't temp = temp.next set the value of temp to be ultimately == to 1 as indicated in by the console log marked out by the red arrow but rather ended up becoming [1,2] as marked out by the blue arrow?
Shouldn't defining a value to a variable actually assign a value to the variable? Such as
var apple = 'apple'
Will give the variable apple the value of 'apple'
But temp = temp.next just seems to to treat the variable temp like a pointer, pointing it to the next node of the linked list and does not actually alter that value of the linked list itself.
1 answers
Answer question0
/**
* 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) {
var list1_head = list1;
let temp = new ListNode(0); //here it create the first node that is not presenti in list1 and list2
let head = temp; //head contains [0, null]
console.log(head);
if(list1 && list2){ //if both lists are defined
while(list1 && list2){ //while they are both defined
if(list1.val < list2.val){ // check if current value of list1 is < of list2
temp.next = list1; //adds the lesser value as the next element on merged list
list1 = list1.next; //list1 became list1 next (so in the next iteration list1.val changes to the next item
}
else{
temp.next = list2; //same as above
list2 = list2.next; //same as above
}
console.log('First Temp');
temp = temp.next; //temp now is the new added node
console.log(temp);
}
}
if(list1){ //list2 is empty and there are some values in list1
temp.next = list1; //add remaining items
}
else if (list2){ //list1 is empty and list2 doesn't
temp.next = list2;//add remaining items from list2
}
console.log('--temp--');
console.log(temp);
console.log("Why isn't the value of temp 1 as set above");
console.log('--head--');
console.log(head);
return head.next; //return head (initial node) minus the first fake node with zero
};
another possible solution of this task is the following
basically you define two function to turn your linked list into array and viceversa and you can use array function to merge and sort and transform it back into linkedList
function ListNode(val, next) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}
const listToArray = list => list === null? []:[list.val, ...listToArray(list.next)]
const arrayToList = arr => arr.reduceRight((res, val) => new ListNode(val, res), null)
const mergeLists = (...lists) => arrayToList(lists.flatMap(listToArray).sort())
console.log(mergeLists( arrayToList([1, 3]), arrayToList([2, 4]), arrayToList([0, -1, 5])))