Algorithm

Palindrome Linked List

Two Pointer Pattern

Palindrome Linked List

Given the head of a singly linked list, return true if the sequence of node values reads the same forwards and backwards (a palindrome), and false otherwise. Only the values are compared. A single-node list is a palindrome; an empty list is too. Aim for O(N) time and O(1) extra space.

CONSTRAINTS
  • Number of nodes: 1 to 100,000
  • 0 <= Node.val <= 9
  • Target: O(N) time and O(1) extra space
EXAMPLE 1
Input: head = [1,2,2,1]
Output: true
Read forward it is 1,2,2,1; read backward it is also 1,2,2,1 — the same sequence.
EXAMPLE 2
Input: head = [1,2,3]
Output: false
Forward is 1,2,3 but backward is 3,2,1. The first and last values already disagree.
EXAMPLE 3
Input: head = [5]
Output: true
A single value reads the same in both directions.
Are values or node identities compared?
Values. Two different nodes holding the same number count as equal.
How are odd-length lists handled?
The single middle value is its own mirror, so it never needs comparing — the two halves around it are what get checked.
Is it acceptable to leave the list reversed at the end?
Often yes, but ask. If the caller reuses the list, reverse the second half back after checking to restore the original order.

Checking a palindrome is something we already know how to do — in Valid Palindrome we put one marker at each end and walked them inward, comparing pairs. But that trick needs to read the sequence from both directions, and a singly linked list only lets you move forward, one .next at a time. There is no way to step backward from the tail, and no index to jump to the k-th-from-last node. So the two-ends walk doesn't fit the shape of the data.

The easy escape, and why we can do better

The simplest fix is to copy every value into an array, where reading from both ends is allowed, and then run the ordinary converging palindrome check on the array. It works and it is O(N) time, but it spends O(N) extra memory on the copy — for a list of 100,000 nodes that is a whole second copy we would like to avoid.

python
vals = []
curr = head
while curr:
    vals.append(curr.val)
    curr = curr.next
left, right = 0, len(vals) - 1
while left < right:
    if vals[left] != vals[right]:
        return False
    left += 1
    right -= 1
return True
Reshape the list so both ends can be walked

If the obstacle is that we can't read the back half backwards, then let's make the back half readable forwards — by physically reversing it in place. That combines two tools you've already built: the fast/slow pointers from Middle of the Linked List to locate the center, and the in-place list reversal from Reverse Linked List. Three steps:

1. Find the middle. Send slow one node at a time and fast two at a time. When fast runs off the end, slow sits at the middle. (This is the same-direction two-pointer idea: two pointers moving the same way at different speeds.)
2. Reverse the second half, starting at slow. Now its links point backward, so its old tail is a new head we can walk forward.
3. Walk the two halves toward the center. One pointer starts at the original head (front half, going forward); the other starts at the head of the reversed second half (which is the original tail). Compare values as they step. This is exactly the converging comparison from Valid Palindrome — we just had to rebuild the list so both "ends" move forward.
python
# 1. Find the middle with fast/slow
slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

# 2. Reverse the second half, from slow onward
prev = None
curr = slow
while curr:
    nxt = curr.next
    curr.next = prev
    prev = curr
    curr = nxt

# 3. Compare the front half against the reversed back half
p1, p2 = head, prev      # prev is the head of the reversed second half
while p2:
    if p1.val != p2.val:
        return False
    p1 = p1.next
    p2 = p2.next
return True
Crucial Notewe stop when p2 (the reversed back half) runs out, not p1. For an odd-length list the two halves overlap on the exact middle value, which is its own mirror and never needs comparing — so the back half is the same length or one shorter, and looping on p2 handles both even and odd lengths without a special case.
Worked example:head = 1 → 2 → 2 → 1
- Find middle: slow steps 1 → 2 → (second) 2 while fast runs off the end. slow rests on the second 2.
- Reverse from the second 2: the back half 2 → 1 becomes 1 → 2, whose head (prev) is the node valued 1.
- Compare: p1=1 vs p2=1 → match. p1=2 vs p2=2 → match. p2 reaches the end with no mismatch. Return true.

For an odd list like 1 → 2 → 1: slow lands on the middle 2, the reversed back half is just 1, and comparing 1 against the head's 1 matches — the middle 2 is never touched, exactly as it should be.

Where this sits in the family

The transferable lesson isn't the palindrome check itself — it's the reflex when a converging idea meets a one-directional structure: transform the data until both ends can be walked forward, using fast/slow to split and reversal to flip. That "find the middle, reverse a half, then merge or compare the two halves" combination is a workhorse for linked lists; you'll use its close twin next in Reorder List. The cost is one pass to find the middle, one to reverse, one to compare — all O(N) time — and because every step just relinks existing nodes, O(1) extra space.

Interactive Strategy Visualization
SYMMETRY SCANNER

Structural Palindrome Verification

1
2
3
2
1
SLOW
FAST
LOCATING MIDPOINT

Current Phase

Phase 1: Finding the Center

We use a Slow and Fast pointer. The Slow pointer lands exactly in the middle when the Fast pointer reaches the end.

Converging Scan

By reversing only half the list, we enable pointers at both ends to move toward each other. This is the Symmetric Scan strategy in action.

O(1) Space Mastery

Unlike strings, linked lists can be modified in-place. We achieve palindrome verification with zero extra memory by temporarily structural changes.

Strategy: Reverse & Reflect

1. Find Mid point → 2. Reverse from Mid to Tail → 3. Converge from both ends to compare.

O(N) Time · O(N) Space Copy to Array
→
O(N) Time · O(1) Space Reverse Half + Converge