educative.io

Educative

More readable solution

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

Hi Nicolas_F,
I have viewed your solution, you are working very hard. Keep it up!

1 Like