Palindrome Linked List

1. Define the problem

Given the head of a singly linked list , return true if it is a palindrome or false otherwise. Use fast and slow pointers to find the middle of the list, then reverse the second half in place and compare it node by node against the first half.

Constraints

The number of nodes in the list is in the range [1, 10⁵]
0 ≤ Node.val ≤ 9

Example

Inputhead = [1, 2, 2, 1]

Outputtrue

Explanation Reading the values forward [1, 2, 2, 1] and backward [1, 2, 2, 1] gives the same sequence.

2. Know the words first

In plain terms

Linked list: A chain of items where each item points to the next one, like a scavenger hunt where each clue tells you where to find the next.
Palindrome: A sequence that reads exactly the same forwards and backwards, like 'level' or the numbers [1, 2, 2, 1].

3. Visualize the solution

Find the middle, reverse the second half, compare

Statusinit

slow=0, fast=0. Fast will advance two nodes for every one node slow advances.

What happens in this step

slow = 0 (value 1), fast = 0 (value 1)

Both pointers start at the head; each loop iteration slow moves one node while fast moves two.

Step 1 of 5

Steps to visualize

Walk a slow pointer one step and a fast pointer two steps at a time to find the middle of the list.
Reverse the second half of the list in place, starting from the node after slow.
Compare the first half and the reversed second half node by node.
If every pair of values matches, the list is a palindrome.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Find the middle, reverse the second half, compare

Statusinit

slow=0, fast=0. Fast will advance two nodes for every one node slow advances.

What happens in this step

slow = 0 (value 1), fast = 0 (value 1)

Both pointers start at the head; each loop iteration slow moves one node while fast moves two.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function isPalindrome(values) {
  function buildList(arr) {
    const dummy = { val: 0, next: null };
    let curr = dummy;
    for (const v of arr) {
      curr.next = { val: v, next: null };
      curr = curr.next;
    }
    return dummy.next;
  }

  function reverseList(head) {
    let prev = null;
    let curr = head;
    while (curr) {
      const next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }
    return prev;
  }

  const head = buildList(values);
  if (!head || !head.next) {
    return true;
  }

  let slow = head;
  let fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  const secondHalf = reverseList(slow.next);
  let result = true;
  let p1 = head;
  let p2 = secondHalf;

  while (p2) {
    if (p1.val !== p2.val) {
      result = false;
      break;
    }
    p1 = p1.next;
    p2 = p2.next;
  }

  slow.next = reverseList(secondHalf);

  return result;
}

Time: O(n)
Space: O(1)

6. Test cases

Test cases

Input	Expected	Covers
`head = [1, 2, 2, 1]`	`true`	example from the docstring
`head = [5]`	`true`	smallest valid input, a single node
`head = [1, 2, 1]`	`true`	odd-length list where the middle node is skipped
`head = [1, 2, 3]`	`false`	not a palindrome, first comparison fails
`head = [1, 2]`	`false`	boundary case, two differing nodes
`head = [7, 7]`	`true`	boundary case, two matching nodes
`head = [1, 2, 3, 4, 2, 1]`	`false`	longer even-length list that fails partway through

Palindrome Linked List