class Node {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
const is_palindromic_linked_list = function (head) {
let middleNode = getMiddleNode(head)
// this will be mutated so...
let reversedSecondHalf = reverseListInPlace(middleNode)
// store a reference so we can restore the original order
let reversedSecondHalfReference = reversedSecondHalf
let ptr1 = head
let ptr2 = reversedSecondHalf
while (ptr1 !== null && ptr2 !== null) {
if (ptr1.value !== ptr2.value) {
break // not a palindrome
}
ptr1 = ptr1.next
ptr2 = ptr2.next
}
// restore order before returning
reverseListInPlace(reversedSecondHalfReference)
// if end of list was reached, we have a palindrome
if (ptr1 === null || ptr2 === null) {
return true
}
return false
}
const getMiddleNode = (head) => {
let slow = head
let fast = head
while (fast !== null && fast.next !== null) {
slow = slow.next
fast = fast.next.next
}
return slow
}
const reverseListInPlace = (head) => {
reversed = null
while (head !== null) {
// store reference to next node
const next = head.next
// reverse order and append reversed list
head.next = reversed
reversed = head
// move forward
head = next
}
return reversed
}
head = new Node(2)
head.next = new Node(4)
head.next.next = new Node(6)
head.next.next.next = new Node(4)
head.next.next.next.next = new Node(2)
console.log(`Is palindrome: ${is_palindromic_linked_list(head)}`)
head.next.next.next.next.next = new Node(2)
console.log(`Is palindrome: ${is_palindromic_linked_list(head)}`)
Type your question above this line.
Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/6490214644056064