My question is about Linked List and Pointers I know linkedlist and how it's work, but my problem is that:
I have this example odd-even linked list :
// This is class node for create nodes
class Node {
constructor(val, next) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
}
// this is our function to return odd nodes followed bt even nodes
// * return the index of node not the value so if node index is 1 and value is 2
// thats mean odd node not even cuz we don't care about value
// consider that index start from 1 not from 0
const oddEvenLinkedList = function (head) {
if (!head) return head;
var odd = head
var even = head.next
var evenHead = even
while (odd.next) {
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
}
odd.next = evenHead
return head;
};
// create our linked list
// Node takes two params Node(value, next_node)
const head = new Node(1,
new Node(2,
new Node(3,
new Node(4,
new Node(5,
new Node(6,
new Node(7)))))))
console.log(oddEvenLinkedList(head));
The result will be :
head = [1,3,5,2,4,6,7] // odd numbers followed by even nubmers
so my question is : what's happened here when we added :
var odd = head
var even = head.next
var evenHead = even
I know the odd
var now will be : [1,2,3,4,5,6]
and at the same time even
will be : [2,3,4,5,6,7]
the problem is : odd
and even
after loop will be equals to:
odd = [7]
even = null
and at the last line when we add : odd.next = evenHead
that's mean odd
will be equal to odd=[7,1,2,3,4,5,6,7]
but when I return odd
will be something like this: odd=[1,3,5,2,4,6,7]
and at the same time when I return head
will be equal to odd
the same result :
head=[1,3,5,2,4,6,7]
why odd
var effects on head
and even
var effect on evenHead
?
I hope you understand what I mean:
simple summary if you don't understand the above explanation
let head = [1,2,3,4,5] // linked list 1->2->3...etc
let x = main
let z = main
//for example when change x or z :
x.next = null
//or
z.next = null // or whatever value
// any changes we do in z or x will affect the head, why?
class Node {
constructor(val, next) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
}
var oddEvenLinkedList = function (head) {
if (!head) return head;
var odd = head
var even = head.next
var evenHead = even
while (odd.next) {
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
}
odd.next = evenHead
return head;
};
const head = new Node(1, new Node(2, new Node(3, new Node(4, new Node(5, new Node(6, new Node(7)))))))
console.log(oddEvenLinkedList(head));
odd.next = evenHead
that meansodd
will be equal toodd=[7,1,2,3,4,5,6,7]
but when I returnodd
it is something like this:odd=[1,3,5,2,4,6,7]
The reason is that the loop has rewired the list. Before the loop executes, the list, starting from head
, is:
odd
head
↓
1→2→3→4→5→6→7
↑
evenHead
even
But the loop redirects all those "arrows", so that after the loop, the links are as follows:
head odd
↓ ↓
1→→→3→→→5→→→7
2→→→4→→→6
↑ ↑
evenHead even
And when the last assignment has been executed, we get the final result:
head odd
↓ ↓
1→→→3→→→5→→→7→→→2→→→4→→→6
↑ ↑
evenHead even
So if then you would look at odd
, you will find the following list sequence: [7, 2, 4, 6]. If the purpose would have been to first get all odd values and then all even values, then the statements after the loop should change from this:
odd.next = evenHead
return head;
to this:
even.next = head
return evenHead;
They would be executed when the state is as follows (I repeat):
head odd
↓ ↓
1→→→3→→→5→→→7
2→→→4→→→6
↑ ↑
evenHead even
But with these final statements we get this:
head odd
↓ ↓
2→→→4→→→6→→→1→→→3→→→5→→→7
↑ ↑
evenHead even
...and then evenHead
would be returned, so the sequence would then be [2, 4, 6, 1, 3, 5, 7].