class Node {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
print_list() {
result = "";
temp = this;
while (temp !== null) {
result += temp.value + " ";
temp = temp.next;
}
console.log(result);
}
}
const reorder = function (head) {
let reversedSecondHalf = reverseListInPlace(getMiddleNode(head))
// head contains only the first original half
// because the reversed second half's last node.next is null
// e.g: 2,4,6,8,null / 12,10,8,null
// ^- same node --^
let firstHalf = head
while (firstHalf !== null && reversedSecondHalf !== null) {
// store references to the original next nodes for iteration
const next = firstHalf.next
const revNext = reversedSecondHalf.next
// set the next node to the head of the reversed half
firstHalf.next = reversedSecondHalf
// move the iteration forward
firstHalf = next
// prevent the last node looping into itself
if (firstHalf !== reversedSecondHalf) {
// set the next node to the head of the first half
reversedSecondHalf.next = firstHalf
}
// move the iteration forward
reversedSecondHalf = revNext
}
// terminate the list
if (firstHalf.next !== null) {
firstHalf.next = null
}
}
const reverseListInPlace = (head) => {
let reversed = null
while (head !== null) {
// store ref to next
const next = head.next
// reverse order
head.next = reversed
reversed = head
// set next iteration
head = next
}
return reversed
}
const getMiddleNode = (head) => {
let slow = head
let fast = head
while (fast !== null && fast.next !== null) {
slow = slow.next
fast = fast.next.next
}
return slow
}
head = new Node(2)
head.next = new Node(4)
head.next.next = new Node(6)
head.next.next.next = new Node(8)
head.next.next.next.next = new Node(10)
head.next.next.next.next.next = new Node(12)
reorder(head)
head.print_list()
Type your question above this line.
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/6429532024209408