Palindrome Linked List (LC 234)

Pattern: Fast & Slow Pointers + Linked List Reversal
Difficulty: Easy
Key Concept: Find middle with fast/slow, reverse second half, compare both halves

1. Problem Statement

Given the head of a singly linked list, return true if it is a palindrome and false otherwise.

A palindrome reads the same forward and backward.

Constraints (typical):

• The number of nodes in the list is in the range [1, 10^5].
• 0 <= Node.val <= 9

Follow-up (conceptual): Solve in O(n) time and O(1) extra space — the optimal pointer + reversal approach below achieves that.

---

2. Algorithm

Brute (copy to array)

Pseudocode:

values = empty list
for p = head; p != null; p = p.next:
    values.add(p.val)
use two pointers left=0, right=values.size()-1
while left < right:
    if values.get(left) != values.get(right): return false
    left++; right--
return true

Optimal (fast/slow + reverse second half + compare)

Pseudocode:

if head == null or head.next == null: return true

// 1) Find middle (slow ends at middle / first middle for even length)
slow = head, fast = head
while fast != null AND fast.next != null:
    slow = slow.next
    fast = fast.next.next

// 2) Reverse list starting at slow (second half)
prev = null, cur = slow
while cur != null:
    next = cur.next
    cur.next = prev
    prev = cur
    cur = next
// prev is head of reversed second half

// 3) Compare first half (from head) with reversed half (from prev)
first = head, second = prev
while second != null:   // second half same length or one shorter
    if first.val != second.val: return false
    first = first.next
    second = second.next
return true

---

3. Beginner Analysis — Three-Step Optimal Approach

1. Find the middle with fast (2 steps) and slow (1 step). When fast reaches the end, slow is at the start of the second half (for odd length, the middle node is included in the half we reverse — we compare only as many nodes as the shorter half needs).
2. Reverse the second half so we can traverse it backward using the same “forward” pointer logic as the first half.
3. Compare first from the original head with second from the reversed tail. If every pair matches, the list is a palindrome.

This avoids O(n) extra storage for values while still touching each node a constant number of times.

Restoring the list: The optimal solution mutates links. To restore the original list you would reverse the second half again and reconnect — doable but rarely required for this problem’s typical “return boolean” contract.

---

4. Dry Run — Values [1,2,2,1]

List: 1 → 2 → 2 → 1

Phase	Action	Result
Start	slow/fast from head	slow at 1, fast at 1
Move 1	fast 2 steps, slow 1	slow at 2 (first 2), fast at 2 (second 2)
Move 2	fast 2 steps, slow 1	slow at 2 (second 2), fast at null → stop
Reverse from slow	reverse 2 → 1	First half head still 1→2; reversed second half 1→2 with prev at first 1
Compare	first: 1,2 second: 1,2	1==1, 2==2 → true

---

5. Brute Force Java — ArrayList + Two Pointers

import java.util.ArrayList;
import java.util.List;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
}

class SolutionBrute {
    public boolean isPalindrome(ListNode head) {
        List<Integer> values = new ArrayList<>();
        for (ListNode p = head; p != null; p = p.next) {
            values.add(p.val);
        }
        int left = 0, right = values.size() - 1;
        while (left < right) {
            if (!values.get(left).equals(values.get(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

---

6. Optimal Java — Fast/Slow + Reverse Second Half + Compare

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode second = reverse(slow);
        ListNode first = head;

        while (second != null) {
            if (first.val != second.val) {
                return false;
            }
            first = first.next;
            second = second.next;
        }
        return true;
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

---

7. Java & Language Tricks

Topic	Note
ArrayList.get(i)	O(1) random access — good for two-pointer palindrome check after copy.
Combines patterns	Fast/slow (pattern 04) + reversal (pattern 07).
Restoring the list	Not trivial after reversal; brute force leaves the list unchanged.

---

8. Complexity

Approach	Time	Space
Brute (ArrayList)	O(n)	O(n)
Optimal (reverse half)	O(n)	O(1) extra

n = number of nodes.