Palindrome Linked List (LC 234)

Pattern: Fast & Slow Pointers + Reverse second half (two-pointer compare)
Difficulty: Easy
Key Concept: For O(1) extra space, find the middle with fast/slow, reverse the second half, then compare the first half with the reversed half node by node.

Problem Statement

Given the head of a singly linked list, return true if the sequence of values reads the same forward and backward (a palindrome), and false otherwise.

Follow-up: Solve in O(n) time and O(1) space (the optimal approach below meets this).

Input: head of a singly linked list (ListNode with int val, ListNode next).

Output: boolean — whether the list is a palindrome.

---

1. Algorithm & Pseudocode

Brute force: copy to array / ArrayList

1. Traverse the list; append each val to an ArrayList<Integer>.
2. Set left = 0, right = size - 1.
3. While left < right:
   • If list.get(left) != list.get(right), return false.
   • left++, right--.
4. Return true.

Optimal: middle + reverse + compare

1. Find middle: Use fast/slow pointers starting at head. Advance slow one step, fast two steps, until fast is null or fast.next is null. After the loop, slow is at the start of the second half (for even length, this is the node after the first middle — adjust if you prefer the first middle; consistency matters for reversal).
2. Reverse second half: Starting from slow, reverse the sublist (iterative three-pointer reversal is standard).
3. Compare: ListNode p1 = head, ListNode p2 = head of reversed part. While p2 != null, compare p1.val and p2.val; advance both. If any mismatch, return false.
4. Return true.

Note on restoring the list: The problem usually only asks for a boolean. Mutating the list is acceptable on LeetCode. Restoring the original links would require reversing the second half again; Java does not pass primitives by reference, but object references (ListNode) are shared — you can still restore by reversing again if an interviewer requires an unchanged list.

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why copy to ArrayList works: A palindrome is symmetric. Random access from both ends matches the definition. ArrayList.get(i) is O(1), so the two-pointer scan on the list is O(n).

Why we need the middle: The second half must be compared to the first half in reverse order. Finding the middle splits the problem: first half forward vs second half backward.

Why reverse the second half: Singly linked lists only go forward. Reversing the second half lets you traverse it “backward” with a simple next walk in sync with the first half.

Why fast/slow for middle: Same as LC 876 — one pass, O(1) space. The exact split point (first vs second middle for even length) must match how you reverse and compare; the template below uses the common LeetCode pattern: after the while loop, if fast != null (odd length), move slow one more step so slow starts the second half.

Java and “pass by reference”: Primitives are passed by value; ListNode references are copied but point to the same objects, so reversing nodes mutates the shared structure. That is why you can compare p1 and p2 without copying nodes again.

---

3. The Dry Run

List: 1 → 2 → 2 → 1 (head at first 1).

Step A — fast/slow to find middle

Step	slow.val	fast	Condition (fast, fast.next)	Action
Init	1	at first node	—	—
1	2	at third node (2)	both OK	slow→2, fast moves 2 steps
2	2	past end (null)	fast null	exit

After loop: slow at second node with value 2 (first node of second half if we treat split here).
(Odd-length variant: sometimes code does if (fast != null) slow = slow.next — for 4 nodes, fast ends null, no extra step.)

Step B — reverse from slow

Second half: 2 → 1 → reverse to 1 → 2. Let prev = null, cur = slow:

Step	cur	cur.next	prev	Action
1	2	1	null	2 points to null, move
2	1	null	2	1 points to 2, move
3	null	—	1	done; new head of reversed half = node with 1 (call it p2 start)

Step C — compare

Step	p1 (from head)	p2 (reversed head)	Match?
1	val 1	val 1	yes
2	val 2	val 2	yes
3	p2 null	—	done → true

---

4. Java Solution

Brute Force

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

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

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

Time: O(n).
Space: O(n) for the ArrayList.

Optimal

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

        // 1) Middle of list (slow starts second half after loop)
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // Odd number of nodes: skip true middle
        if (fast != null) {
            slow = slow.next;
        }

        // 2) Reverse second half
        ListNode prev = null;
        while (slow != null) {
            ListNode next = slow.next;
            slow.next = prev;
            prev = slow;
            slow = next;
        }

        // 3) Compare first half with reversed second half
        ListNode p1 = head;
        ListNode p2 = prev;
        while (p2 != null) {
            if (p1.val != p2.val) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
    }
}

Time: O(n).
Space: O(1) extra (only pointer variables).

---

5. The “Java vs. Others” Edge

• ArrayList brute force: list.get(i) is O(1) amortized, like std::vector in C++ or a Python list — same two-pointer-from-ends idea.
• Optimal combines patterns: Fast/slow (middle) + iterative reversal (three pointers: prev, cur, next) + two-pointer compare. This is a standard LeetCode combo.
• Restoring the list: The optimal solution mutates next pointers. If you must leave the list unchanged, reverse the second half again after the check. Java does not let you “pass head by reference” to reassign the caller’s variable inside a helper for primitives, but ListNode objects are mutable — you restore links on the same nodes.
• Integer vs int in ArrayList: ArrayList stores Integer; using equals in the brute-force compare avoids accidental pitfalls with == on cached small integers in other contexts (for values in list nodes, int unboxing usually works with != on primitives if you compare int — the sample uses Integer.equals for clarity).

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n)	O(n)	Copy values; random access with two indices.
Optimal	O(n)	O(1)	Find middle, reverse second half, compare; mutates list unless restored.