#234 Palindrome Linked List

frequently reported atAmazon Meta Microsoft

the problem

In plain words

Given the head of a singly linked list, return true if its values read the same from front to back as from back to front.

in head = [1,2,2,1]

out true

in head = [1,2]

out false

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

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternFast & slow pointers In-place linked-list rewiring

A singly linked list can't be walked backwards — so make its second half walk backwards. Find the middle with slow/fast, reverse the second half in place, and compare the two halves node by node.

solutions

From brute force to optimal

An array can be read from both ends, so copy the values and run two pointers inwards.

Copy every value into a list.
i = 0, j = size − 1: compare and move inwards.
Any mismatch → false; pointers cross → true.

timeO(n)

One pass to copy, half a pass to compare.

spaceO(n)

The list holds all n values.

javajava.util.*

1class Solution {2    public boolean isPalindrome(ListNode head) {3        List<Integer> vals = new ArrayList<>();          // arrays can read both ends in O(1)4        for (ListNode p = head; p != null; p = p.next) vals.add(p.val);5        int i = 0, j = vals.size() - 1;6        while (i < j) {7            if (!vals.get(i).equals(vals.get(j))) return false; // Integer: compare with equals, not ==8            i++;9            j--;10        }11        return true;12    }13}

slow/fast finds the end of the first half; reverse what follows; walk both halves together; reverse back.

slow = fast = head; while fast.next and fast.next.next exist: slow += 1, fast += 2.
second = reverse(slow.next).
Walk p1 from head and p2 from second; any different pair → not a palindrome.
slow.next = reverse(second) to restore the list; return the answer.

timeO(n)

A few linear passes: find the middle, reverse, compare, reverse back.

spaceO(1)

Only a handful of references; the reversal happens in place.

javajava.util.*

1class Solution {2    public boolean isPalindrome(ListNode head) {3        ListNode slow = head, fast = head;4        while (fast.next != null && fast.next.next != null) { // slow stops at the end of the first half5            slow = slow.next;6            fast = fast.next.next;7        }8        ListNode second = reverse(slow.next); // second half, now read back to front9        boolean same = true;10        ListNode p1 = head, p2 = second;11        while (same && p2 != null) { // the second half is never longer than the first12            if (p1.val != p2.val) same = false;13            p1 = p1.next;14            p2 = p2.next;15        }16        slow.next = reverse(second); // put the list back the way we found it17        return same;18    }19 20    private ListNode reverse(ListNode head) {21        ListNode prev = null;22        while (head != null) {23            ListNode next = head.next;24            head.next = prev;25            prev = head;26            head = next;27        }28        return prev;29    }30}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public boolean isPalindrome(ListNode head) {3        ListNode slow = head, fast = head;4        while (fast.next != null && fast.next.next != null) { // slow stops at the end of the first half5            slow = slow.next;6            fast = fast.next.next;7        }8        ListNode second = reverse(slow.next); // second half, now read back to front9        boolean same = true;10        ListNode p1 = head, p2 = second;11        while (same && p2 != null) { // the second half is never longer than the first12            if (p1.val != p2.val) same = false;13            p1 = p1.next;14            p2 = p2.next;15        }16        slow.next = reverse(second); // put the list back the way we found it17        return same;18    }19 20    private ListNode reverse(ListNode head) {21        ListNode prev = null;22        while (head != null) {23            ListNode next = head.next;24            head.next = prev;25            prev = head;26            head = next;27        }28        return prev;29    }30}

in the room

How to say it in the interview

talk track

Give the array version first: correct, O(n) time, but O(n) space.
Then: "For O(1) space I'll reuse two moves from this chapter — find the middle, reverse the second half."
Say why the compare loop stops on the second half: it is never longer than the first.
Mention restoring the list: a check shouldn't leave the caller's data changed.

traps

Using the second-middle loop (fast != null && fast.next != null) and then reversing slow.next: for even lengths you skip one node of the second half, so [1,2,3,1] wrongly passes.
Comparing boxed Integers with == in the array version — fine for 0–9 thanks to Java's small-integer cache, wrong in general. Use equals or an int[].
Forgetting to restore the list after reversing its second half.

what they ask next

Follow-ups

Can you avoid changing the list at all, even temporarily?

Recursion with a front pointer: recurse to the tail, and on the way back compare each node with front, moving front forward. No changes, but O(n) stack — 10⁵ frames can overflow.

Is the string version easier?

Yes — Valid Palindrome (LC 125) has O(1) access to both ends, so plain two pointers from the ends work.

before you submit

Edge cases to test

One node → true.
Two nodes: equal → true, different → false.
Odd length: the middle node needs no partner.
A mismatch right next to the middle, like [1,2,3,4,2,1].

practise next