islistpalimdromenotests.js

const isPalindrome = (head) => {
  // zero and single element lists are always symmetric
  if (head === null || head.next === null) return true;

  let fast = head;
  let slow = head;
  // fast pointer technique
  // since fast traverses whole list and moves 2x as fast
  // it makes sense how slow can be only halfway through
  // if list is odd, fast will end up being not being null
  // len(l) -> 2: s0 f0 s1 fnull
  // len(l) -> 3: s0 f0 s1 f2
  // len(l) -> 4: s0 f0 s1 f2 s2 fnull
  while (fast && fast.next !== null) {
      slow = slow.next;
      fast = fast.next;
      fast = fast.next;
  }
    const newHead = reverseFromTo(head, slow);
  // makes odd length lists work
  if (fast) {
    // if odd, we do not want to compare the middle
    slow = slow.next;
  }
    let first = newHead;
    let second = slow;
    while (second !== null) {
        if (first.value !== second.value) return false;
        first = first.next;
        second = second.next;
    }
 return true;
}
// reverses linked list starting from head to stopAt exclusive
const reverseFromTo = (head, stopAt) => {
    // I recommend trying 1, 2, 3 and 3 and walking through this algorithm
    // to find that it will return 2 1 3
    let current = head;
    let previous = stopAt;
    while (current !== stopAt) {
        next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }
    return previous;
}