Palindrome Linked List

EasyLinked List · Fast & Slow Pointers · In-place Reversal🧩 Linked List Techniques LeetCode #234 ↗Updated Oct 30, 2026

Problem

You get the head of a singly linked list of digits. Return true if the sequence of values reads the same forwards and backwards, otherwise false. You can only walk the list forwards.

Input[1,2,2,1]Outputtrue

Input[1,2]Outputfalse

Input[3,1,3]Outputtrue

1 ≤ n ≤ 10⁵ · 0 ≤ Node.val ≤ 9 · Follow-up: O(n) time and O(1) extra space.

Try it yourself

Java

class Solution {
    public boolean isPalindrome(ListNode head) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A palindrome means the second half, read backwards, equals the first half. Find the middle with fast/slow pointers, reverse the second half in place, and the two halves can be compared walking forwards.

PatternLinked List Techniques

Instinct Nodes joined by next pointers and the task is to reverse, splice, merge, reorder or remove in place - grab a dummy head and rewire pointers carefully.

Memory hack Save next, flip, step - never let go of a rope before you've grabbed the next one.

Open the Linked List Techniques guide →

Approaches

Brute ForceCopy Values to an Array, Two Pointers

Time O(n)Space O(n)

Arrays allow walking from both ends, lists do not. Dump all values into an ArrayList, then move i from the left and j from the right, comparing as they meet in the middle.

Java

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

Simple and safe, but stores a full copy of the list.

BetterStack the First Half (Fast/Slow)

Time O(n)Space O(n/2)

While fast jumps two nodes, slow jumps one and pushes its value, so when fast runs out the stack holds exactly the first half. Skip the middle node for odd lengths, then pop while walking the second half — the stack gives the first half in reverse.

Java

public boolean isPalindrome(ListNode head) {
    Deque<Integer> stack = new ArrayDeque<>();
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        stack.push(slow.val);
        slow = slow.next;
        fast = fast.next.next;
    }
    if (fast != null) slow = slow.next; // odd length: skip the middle
    while (slow != null) {
        if (stack.pop() != slow.val) return false;
        slow = slow.next;
    }
    return true;
}

One pass and half the memory, but still not the O(1) follow-up.

OptimalReverse the Second Half, Compare, Restore

Time O(n)Space O(1)

Stop slow at the end of the first half, reverse the list after it, and walk both halves in lock-step comparing values. The second half is never longer than the first, so it drives the loop. Reverse it back afterwards so the caller's list is unchanged.

Java

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true;
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;       // ends at the last node of the first half
        fast = fast.next.next;
    }
    ListNode second = reverse(slow.next);
    boolean same = true;
    for (ListNode p = head, q = second; q != null; p = p.next, q = q.next) {
        if (p.val != q.val) {
            same = false;
            break;
        }
    }
    slow.next = reverse(second); // put the list back as we found it
    return same;
}

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

Meets the follow-up: linear time, constant memory, input restored.

Pro tip

Mention restoring the list — interviewers like seeing that you don't leave the caller's data mangled.

At a glance

Level	Approach	Time	Space
Brute Force	Copy Values to an Array, Two Pointers	`O(n)`	`O(n)`
Better	Stack the First Half (Fast/Slow)	`O(n)`	`O(n/2)`
Optimal	Reverse the Second Half, Compare, Restore	`O(n)`	`O(1)`

Common pitfalls

Comparing boxed Integers with == — works only for small values by caching luck.
Wrong middle for odd lengths — the centre node must be skipped (or ignored), not compared.
Breaking out of the compare loop before restoring the reversed half.

Interview tips

Start from the array copy, then ask whether O(1) space is required.
Explain why the fast/slow stop condition puts slow at the end of the first half.
Test aloud: single node, two equal nodes, two different nodes, odd length.

Pattern

Find middle + reverse half → compare or interleave the two halves of a singly linked list in O(1) space.

My notes saved in this browser