Loading…

easyLinked ListsLC #234Frequently asked

Palindrome Linked List

Q: How do you solve Palindrome Linked List using the Copy to Array — Two-Pointer Compare approach?

When to use it: State this first as the obviously-correct baseline. It's the safe answer when mutation is forbidden or O(n) space is fine. Flatten the list into an array of values, then run the standard array-palindrome check with two pointers converging from the ends. **Why this is the natural first answer.** Palindrome checking is trivial on a structure with random access: compare index `i` with index `n-1-i` for `i` up to the middle. A singly linked list lacks random access and can't be walked backwards, so the simplest fix is to *give* ourselves random access by copying the values into an array. Now the textbook two-pointer compare applies directly. **Why we compare values, not nodes.** A palindrome is about the *sequence of values*, so once the values are in the array the original nodes are irrelevant. This also sidesteps any concern about mutating the list — we never touch the links. **Why two pointers from the ends.** Moving `left` up from `0` and `right` down from `n-1`, comparing as we go, checks the i-th symmetric pair in O(1) each. The moment a pair disagrees we can short-circuit to `false`; if they meet or cross, every symmetric pair matched and it's a palindrome. **Why we ultimately prefer the O(1)-space method.** This solution is correct and easy to get right under pressure, which is why it's worth stating. But it uses O(n) auxiliary space, and the explicit follow-up asks for O(1). So we present this for clarity and then upgrade — showing the interviewer both that we can ship something correct fast and that we can optimise when pushed. Time complexity: O(n). Space complexity: O(n).

LCPractice

Linked List · 10 of 24 · 10 min

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

A list is a palindrome when the sequence of node values reads the same forwards and backwards.

Follow-up: Could you do it in O(n) time and O(1) extra space?

In plain English

We compare the value sequence against its reverse. The trivial check copies values to an array and uses two pointers from both ends. The interview-grade follow-up demands O(1) space: split the list at its middle, reverse the second half in place, and walk both halves inward-to-outward comparing values. Only the values matter — node identity doesn't — but because we mutate pointers to achieve O(1) space, leaving the list intact is a thoughtful extra.

Examples

Example 1

Input: head = [1, 2, 2, 1]
Output: true
Note: Even length. Middle splits into [1, 2] and [2, 1]; reversing the second gives [1, 2], which matches the first half.

Example 2

Input: head = [1, 2, 3, 2, 1]
Output: true
Note: Odd length. Middle node 3 pairs with itself; first half [1, 2] vs reversed back half [1, 2] match.

Example 3

Input: head = [1, 2]
Output: false
Note: Reversed second half [2] compared to first [1] — 1 ≠ 2, not a palindrome.

Constraints

The number of nodes in the list is in the range [1, 10⁵]
0 ≤ Node.val ≤ 9
A single node and an empty list are considered palindromes

Clarifying questions4First question: Am I allowed to modify the list, or must it stay intact?Explore questions

Q1.Am I allowed to modify the list, or must it stay intact?
The O(1)-space method reverses the second half in place. If the list must stay intact, I'll reverse that half back before returning — same complexity, just one extra pass.
Q2.Is O(n) space acceptable, or do you want the O(1)-space follow-up?
I'll mention the O(n)-space array copy for clarity, then implement the O(1)-space reverse-half version since that's the follow-up interviewers want.
Q3.How should I treat empty or single-node lists?
Both are palindromes — return true. The algorithm handles them naturally: the comparison loop simply doesn't run, or runs zero useful times.
Q4.Are the values simple comparables?
Yes, integers here. I compare with ==; for richer payloads I'd compare with the appropriate equality.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

For O(1) space: find the middle with fast/slow pointers, reverse the second half in place, then walk the first half and the reversed second half forward comparing values node-by-node. If every pair matches it's a palindrome. The cheap-and-clear alternative is to copy all values into an array and use two-pointer comparison — O(n) time but O(n) space. Optionally restore the reversed half before returning to leave the input untouched.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can compose the midpoint and reversal primitives into an O(1)-space solution, rather than defaulting to the O(n)-space array copy — and whether you handle odd lengths and (ideally) restore the list.

Where candidates slip

Comparing against the wrong length (looping until the first-half pointer ends rather than the reversed second half), or mishandling the odd-length middle node so the comparison is off by one.

How to stand out

Offer the simple array solution first to anchor correctness, then upgrade to the O(1)-space reverse-half method, explicitly handle the odd middle, and mention restoring the list to leave the input pristine.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Copy to Array — Two-Pointer Compare	`O(n)`	`O(n)`	State this first as the obviously-correct baseline. It's the safe answer when mutation is forbidden or O(n) space is fine.	Read
2	Reverse Second Half — O(1) Space (Optimal)Optimal	`O(n)`	`O(1)`	The follow-up answer. Frame it as 'compose three primitives: find middle, reverse the back half, compare the halves'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewIs the linked list a palindrome?Is O(1) extra space required?No / mutation bannedYesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Copy to Array — Two-Pointer Compare

TimeO(n)SpaceO(n)

State this first as the obviously-correct baseline. It's the safe answer when mutation is forbidden or O(n) space is fine.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A palindrome reads the same forwards and backwards. If the values were in an array, how would you check that in one pass?

2Hint 2Explore hint

Copy every node's value into an array, then use two pointers — one at each end — moving inward and comparing.

3Hint 3Explore hint

If any left/right pair differs, return false; if the pointers cross without a mismatch, return true. O(n) time but O(n) space for the array.

A · Core idea

Flatten the list into an array of values, then run the standard array-palindrome check with two pointers converging from the ends.

Why this is the natural first answer. Palindrome checking is trivial on a structure with random access: compare index i with index n-1-i for i up to the middle. A singly linked list lacks random access and can't be walked backwards, so the simplest fix is to give ourselves random access by copying the values into an array. Now the textbook two-pointer compare applies directly.

Why we compare values, not nodes. A palindrome is about the sequence of values, so once the values are in the array the original nodes are irrelevant. This also sidesteps any concern about mutating the list — we never touch the links.

Why two pointers from the ends. Moving left up from 0 and right down from n-1, comparing as we go, checks the i-th symmetric pair in O(1) each. The moment a pair disagrees we can short-circuit to false; if they meet or cross, every symmetric pair matched and it's a palindrome.

Why we ultimately prefer the O(1)-space method. This solution is correct and easy to get right under pressure, which is why it's worth stating. But it uses O(n) auxiliary space, and the explicit follow-up asks for O(1). So we present this for clarity and then upgrade — showing the interviewer both that we can ship something correct fast and that we can optimise when pushed.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

head = [1, 2, 2, 1]

copy

collect values

Statevals = [1, 2, 2, 1]

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; }Explore the full code

solution.javaJava

Copy to Array — Two-Pointer Compare — reference

3 teaching notes

1
public class ListNode {
2
    int val;
3
    ListNode next;
4
    ListNode() {}
5
    ListNode(int val) { this.val = val; }
6
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
7
}
8
 
9
public boolean isPalindrome(ListNode head) {
10
    List<Integer> vals = new ArrayList<>();
11
    // Flatten the list into an array so we gain random access for the symmetric
12
    // compare.
13
    for (ListNode p = head; p != null; p = p.next) {
14
        vals.add(p.val);
15
    }
16
    int left = 0, right = vals.size() - 1;
17
    while (left < right) {
18
        // Use .equals on boxed Integers — == compares references and breaks above the
19
        // Integer cache (127).
20
        if (!vals.get(left).equals(vals.get(right))) {
21
            return false;
22
        }
23
        // Converge from both ends, checking the i-th symmetric pair each step.
24
        left++;
25
        right--;
26
    }
27
    return true;
28
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.28 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Copying to an array is the universal 'I can't index this structure, so I'll borrow indexing' move. It instantly reduces a linked-list problem to its array form — a great first answer that also makes the O(1)-space optimisation easy to motivate by contrast.

ComplexityO(n) time, O(n) space — One pass to copy n values into an array (O(n) time, O(n) space), then at most n/2 comparisons walking the two pointers inward (O(n) time). Total O(n) time, O(n) space.

E · Edge cases and pitfalls5head = [1] — vals = [1], left=0 not < right=0 → loop skipped, return true. Single node is a palindrome.Explore edge cases

Edge cases handled

head = [1]vals = [1], left=0 not < right=0 → loop skipped, return true. Single node is a palindrome.
head = []vals empty, right = -1, loop skipped → true. Empty list is a palindrome.

Pitfalls

In Java, comparing boxed Integers with == instead of .equals — fails for values cached outside −128..127 (not an issue here with 0..9, but a habit to avoid).
Off-by-one on the right pointer (starting at size() instead of size()-1).
Presenting this as final when the follow-up explicitly asks for O(1) space.

03.2

Approach 2 of 2 · Optimal

Reverse Second Half — O(1) Space (Optimal)

TimeO(n)SpaceO(1)

The follow-up answer. Frame it as 'compose three primitives: find middle, reverse the back half, compare the halves'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A palindrome means the first half equals the reversed second half. You already know how to find the middle and how to reverse a list — can you combine them?

2Hint 2Explore hint

Step 1: fast/slow pointers to reach the middle. Step 2: reverse the list from the middle to the end. Step 3: walk the first half and the reversed second half together, comparing values.

3Hint 3Explore hint

Loop the comparison while the reversed (second-half) pointer is non-null — it's the shorter or equal side, so an odd middle node is skipped harmlessly. Optionally reverse the second half back to restore the input.

A · Core idea

We exploit a clean definition: a list is a palindrome exactly when its first half equals its second half read backwards. Rather than copy anything, we physically reverse the back half so it can be read 'backwards' by walking forward, then compare the two halves in lockstep.

Step 1 — split with fast/slow. Run the tortoise-and-hare midpoint finder. When fast falls off the end, slow sits at the start of the second half (for even lengths) or on the middle node (for odd lengths). This is the same primitive as Middle of the Linked List, reused verbatim — a sign you've decomposed the problem well.

Step 2 — reverse from slow. Apply the standard prev/curr/next three-pointer flip starting at slow. After this, prev is the head of the reversed second half — i.e. the original last node. The first half still runs forward from head. Crucially, for odd lengths the lone middle node ends up as the tail of both conceptual halves, and it simply pairs with itself, so it never causes a mismatch.

Step 3 — compare inward-to-outward. Walk left from head and right from prev simultaneously, comparing left.val == right.val. Why we stop when `right` hits null: the reversed second half is the shorter-or-equal side (it never exceeds half the list), so using it as the loop guard checks every meaningful pair without overrunning. For odd lengths, right reaches null exactly when the unmatched middle would come up, so we never wrongly compare it. If any pair differs we return false; surviving the loop means it's a palindrome.

Optional step 4 — restore. Because we mutated the back half, the caller's list is now altered. Reversing the second half again puts every pointer back, leaving the input pristine at the cost of one more O(n) pass and no extra space. Mentioning this unprompted signals senior-level care about side effects.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

head = [1, 2, 3, 2, 1]

Interactive diagram

Split, reverse, compare

find mid

Active call / nodeSupporting contextReturned stateNot active

Fast/slow splits the list; the back half is flipped so a forward walk reads it backwards; halves are then compared.

Final resulttrue

C · Code with teaching comments

solution.javaJava

Reverse Second Half — O(1) Space (Optimal) — optimal

7 teaching notes

1
public boolean isPalindrome(ListNode head) {
2
    // Empty or single-node lists are trivially palindromes — short-circuit.
3
    if (head == null || head.next == null) {
4
        return true;
5
    }
6
    // 1. find middle (slow ends at start of 2nd half / the middle)
7
    ListNode slow = head, fast = head;
8
    // Fast/slow midpoint; slow lands at the start of the second half (even) or the
9
    // middle (odd).
10
    while (fast != null && fast.next != null) {
11
        slow = slow.next;
12
        fast = fast.next.next;
13
    }
14
    // 2. reverse from slow to the end
15
    // Reverse starting at slow — prev becomes the head of the reversed back half.
16
    ListNode prev = null, curr = slow;
17
    while (curr != null) {
18
        ListNode nxt = curr.next;
19
        curr.next = prev;
20
        prev = curr;
21
        curr = nxt;
22
    }
23
    // 3. compare first half with reversed second half
24
    // left walks the original first half; right walks the reversed second half.
25
    ListNode left = head, right = prev;
26
    boolean ok = true;
27
    // Guard on the reversed half (the shorter side) so the odd middle node is skipped
28
    // harmlessly.
29
    while (right != null) {
30
        // Any mismatched symmetric pair means it's not a palindrome.
31
        if (left.val != right.val) {
32
            ok = false;
33
            break;
34
        }
35
        left = left.next;
36
        right = right.next;
37
    }
38
    // 4. (optional) restore the second half
39
    // Optional restore: reverse the second half again so the caller's list is
40
    // untouched.
41
    ListNode prev2 = null, cur2 = prev;
42
    while (cur2 != null) {
43
        ListNode nxt = cur2.next;
44
        cur2.next = prev2;
45
        prev2 = cur2;
46
        cur2 = nxt;
47
    }
48
    return ok;
49
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.49 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

This is two well-known primitives bolted together: midpoint via fast/slow and in-place reversal via prev/curr/next. The meta-skill is recognising that a hard-looking problem is really 'find middle' + 'reverse' + 'compare' — decomposition beats cleverness, and the same split+reverse opens Reorder List too.

ComplexityO(n) time, O(1) space — Finding the middle is one pass (O(n)). Reversing the second half touches n/2 nodes (O(n)). Comparing walks n/2 pairs (O(n)). All sequential, no extra data structure → O(n) time, O(1) space.

E · Edge cases and pitfalls7head = [1, 2, 2, 1] — Even length. slow lands on the 3rd node; reversed back half [1, 2]; compares to [1, 2] → true.Explore edge cases

Edge cases handled

head = [1, 2, 2, 1]Even length. slow lands on the 3rd node; reversed back half [1, 2]; compares to [1, 2] → true.
head = [1, 0, 1]Odd length. Middle 0 pairs with itself; left/right both see [1] before right hits null → true.
head = [1, 2]slow→2, reversed back half [2], compare 1 vs 2 → mismatch → false.

Pitfalls

Looping the comparison while `left != null` instead of `right != null` — overruns on the odd middle and can misread.
Forgetting that the reverse mutates the input; if the list must stay intact, restore it.
Skipping the empty/single-node short-circuit and then dereferencing null in the midpoint loop.
Reversing from head.next or the wrong node instead of slow — misaligns the halves.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic boolean isPalindrome(ListNode head) { if (head == null || head.next == null) { return true; } // 1. find middle (slow ends at start of 2nd half / the middle)Explore the playground

Try it — Java· run a complete program; method snippets need a driver

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    // 1. find middle (slow ends at start of 2nd half / the middle)
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // 2. reverse from slow to the end
    ListNode prev = null, curr = slow;
    while (curr != null) {
        ListNode nxt = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nxt;
    }
    // 3. compare first half with reversed second half
    ListNode left = head, right = prev;
    boolean ok = true;
    while (right != null) {
        if (left.val != right.val) {
            ok = false;
            break;
        }
        left = left.next;
        right = right.next;
    }
    // 4. (optional) restore the second half
    ListNode prev2 = null, cur2 = prev;
    while (cur2 != null) {
        ListNode nxt = cur2.next;
        cur2.next = prev2;
        prev2 = cur2;
        cur2 = nxt;
    }
    return ok;
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong comparison loop guard

The reversed second half is the shorter-or-equal side. Guarding on the first-half pointer (left) instead of right makes the loop run one step too long on odd lengths, dereferencing past the intended pairs.

Explore the code comparison

Don't write this

left, right = head, prev
while left:            # first half is longer on odd lengths
    if left.val != right.val:
        return False
    left = left.next
    right = right.next  # right becomes None, then .val crashes

Write this instead

left, right = head, prev
while right:           # reversed half is the safe, shorter guard
    if left.val != right.val:
        return False
    left = left.next
    right = right.next

Not restoring a mutated list

The O(1)-space method reverses the back half in place. If the caller still needs the original list (or tests it afterward), leaving it reversed is a silent corruption bug.

Explore the code comparison

Don't write this

# ... compare halves ...
return ok   # list's second half is left reversed

Write this instead

# ... compare halves ...
prev2, cur2 = None, prev
while cur2:
    nxt = cur2.next
    cur2.next = prev2
    prev2 = cur2
    cur2 = nxt
return ok   # original order restored

Crashing the midpoint loop on tiny lists

Without an empty/single-node guard, the same fast.next.next dereference risk applies; and for a clean structure, short-circuiting trivial palindromes is clearer.

Explore the code comparison

Don't write this

ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) { // NPE if head is null
    slow = slow.next;
    fast = fast.next.next;
}

Write this instead

if (head == null || head.next == null) return true;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Fast/slow midpoint + reverse second half + two-pointer compare

Code pattern to memorize

# 1. find middle
slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
# 2. reverse from slow
prev = None
while slow:
    nxt = slow.next; slow.next = prev; prev = slow; slow = nxt
# 3. compare halves
left, right = head, prev
while right:
    if left.val != right.val: return False
    left = left.next; right = right.next
return True

Rules to remember

1Find the middle with fast/slow, then reverse from slow to the end — you compare the first half against the reversed second half.
2Stop the comparison when the second-half (right) pointer hits null; the reversed half is the shorter/equal one, so it's the safe loop guard.
3An odd-length list has a lone middle node that pairs with itself — the right-half walk naturally stops before forcing it to match anything.
4Reversing mutates the input. If the caller must see the original list, reverse the second half back before returning.
5Use fast and fast.next for the midpoint so fast.next.next never dereferences null.
6The array approach is O(n) space but trivially correct — name it as the fallback, then offer the O(1) reverse-half method as the upgrade.

Use this pattern when

Check symmetry of a singly linked list with O(1) extra space
Any problem needing the reversed second half compared against the first (Reorder List shares the split+reverse)
Demonstrating composition of two primitives: midpoint-finding and in-place reversal
When recursion depth (O(n) stack) or an array copy (O(n) space) is unacceptable

Choose another pattern when

Mutating the input is forbidden and you can't restore it → copy values to an array instead
It's a doubly linked list → walk inward from both ends, no reversal needed
Values are huge objects, not cheap ints → comparison cost may dominate; reconsider copying

Interview takeaway

Palindrome Linked List is the textbook 'compose two primitives' problem: fast/slow to split, three-pointer flip to reverse, then a linear compare. If you've mastered Middle of the Linked List and Reverse Linked List, this is just gluing them together — and that composition mindset is exactly what interviewers reward.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical composition of fast/slow midpoint + in-place reversal + linear compare. The split-then-reverse setup is shared with Reorder List, the reversal subroutine is Reverse Linked List, and the midpoint step is Middle of the Linked List. Recognise it whenever you must compare a list against its own reverse without extra space.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Reverse Linked List
The reversal of the second half is exactly this prev/curr/next flip — the core subroutine here.
Middle of the Linked List
The fast/slow split that begins this solution is this problem in isolation.
Reorder List
Same split-then-reverse setup, but interleave the two halves instead of comparing them.
Palindrome Number
Coming soon
Same palindrome idea on an integer's digits — reverse half the number and compare.

Same pattern

←

Middle of the Linked List

Continue · Next problem

Reverse Linked List II

easyLinked ListsLC #234Frequently asked

Palindrome Linked List

LCPractice

Linked List · 10 of 24 · 10 min

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

A list is a palindrome when the sequence of node values reads the same forwards and backwards.

Follow-up: Could you do it in O(n) time and O(1) extra space?

In plain English

Examples

Example 1

Input: head = [1, 2, 2, 1]
Output: true
Note: Even length. Middle splits into [1, 2] and [2, 1]; reversing the second gives [1, 2], which matches the first half.

Example 2

Input: head = [1, 2, 3, 2, 1]
Output: true
Note: Odd length. Middle node 3 pairs with itself; first half [1, 2] vs reversed back half [1, 2] match.

Example 3

Input: head = [1, 2]
Output: false
Note: Reversed second half [2] compared to first [1] — 1 ≠ 2, not a palindrome.

Constraints

The number of nodes in the list is in the range [1, 10⁵]
0 ≤ Node.val ≤ 9
A single node and an empty list are considered palindromes

Clarifying questions4First question: Am I allowed to modify the list, or must it stay intact?Explore questions

Q1.Am I allowed to modify the list, or must it stay intact?
The O(1)-space method reverses the second half in place. If the list must stay intact, I'll reverse that half back before returning — same complexity, just one extra pass.
Q2.Is O(n) space acceptable, or do you want the O(1)-space follow-up?
I'll mention the O(n)-space array copy for clarity, then implement the O(1)-space reverse-half version since that's the follow-up interviewers want.
Q3.How should I treat empty or single-node lists?
Both are palindromes — return true. The algorithm handles them naturally: the comparison loop simply doesn't run, or runs zero useful times.
Q4.Are the values simple comparables?
Yes, integers here. I compare with ==; for richer payloads I'd compare with the appropriate equality.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Comparing against the wrong length (looping until the first-half pointer ends rather than the reversed second half), or mishandling the odd-length middle node so the comparison is off by one.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Copy to Array — Two-Pointer Compare	`O(n)`	`O(n)`	State this first as the obviously-correct baseline. It's the safe answer when mutation is forbidden or O(n) space is fine.	Read
2	Reverse Second Half — O(1) Space (Optimal)Optimal	`O(n)`	`O(1)`	The follow-up answer. Frame it as 'compose three primitives: find middle, reverse the back half, compare the halves'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Copy to Array — Two-Pointer Compare

TimeO(n)SpaceO(n)

State this first as the obviously-correct baseline. It's the safe answer when mutation is forbidden or O(n) space is fine.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A palindrome reads the same forwards and backwards. If the values were in an array, how would you check that in one pass?

2Hint 2Explore hint

Copy every node's value into an array, then use two pointers — one at each end — moving inward and comparing.

3Hint 3Explore hint

If any left/right pair differs, return false; if the pointers cross without a mismatch, return true. O(n) time but O(n) space for the array.

A · Core idea

Flatten the list into an array of values, then run the standard array-palindrome check with two pointers converging from the ends.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

head = [1, 2, 2, 1]

copy

collect values

Statevals = [1, 2, 2, 1]

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; }Explore the full code

solution.javaJava

Copy to Array — Two-Pointer Compare — reference

3 teaching notes

1
public class ListNode {
2
    int val;
3
    ListNode next;
4
    ListNode() {}
5
    ListNode(int val) { this.val = val; }
6
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
7
}
8
 
9
public boolean isPalindrome(ListNode head) {
10
    List<Integer> vals = new ArrayList<>();
11
    // Flatten the list into an array so we gain random access for the symmetric
12
    // compare.
13
    for (ListNode p = head; p != null; p = p.next) {
14
        vals.add(p.val);
15
    }
16
    int left = 0, right = vals.size() - 1;
17
    while (left < right) {
18
        // Use .equals on boxed Integers — == compares references and breaks above the
19
        // Integer cache (127).
20
        if (!vals.get(left).equals(vals.get(right))) {
21
            return false;
22
        }
23
        // Converge from both ends, checking the i-th symmetric pair each step.
24
        left++;
25
        right--;
26
    }
27
    return true;
28
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.28 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5head = [1] — vals = [1], left=0 not < right=0 → loop skipped, return true. Single node is a palindrome.Explore edge cases

Edge cases handled

head = [1]vals = [1], left=0 not < right=0 → loop skipped, return true. Single node is a palindrome.
head = []vals empty, right = -1, loop skipped → true. Empty list is a palindrome.

Pitfalls

In Java, comparing boxed Integers with == instead of .equals — fails for values cached outside −128..127 (not an issue here with 0..9, but a habit to avoid).
Off-by-one on the right pointer (starting at size() instead of size()-1).
Presenting this as final when the follow-up explicitly asks for O(1) space.

03.2

Approach 2 of 2 · Optimal

Reverse Second Half — O(1) Space (Optimal)

TimeO(n)SpaceO(1)

The follow-up answer. Frame it as 'compose three primitives: find middle, reverse the back half, compare the halves'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A palindrome means the first half equals the reversed second half. You already know how to find the middle and how to reverse a list — can you combine them?

2Hint 2Explore hint

Step 1: fast/slow pointers to reach the middle. Step 2: reverse the list from the middle to the end. Step 3: walk the first half and the reversed second half together, comparing values.

3Hint 3Explore hint

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

head = [1, 2, 3, 2, 1]

Interactive diagram

Split, reverse, compare

find mid

Active call / nodeSupporting contextReturned stateNot active

Fast/slow splits the list; the back half is flipped so a forward walk reads it backwards; halves are then compared.

Final resulttrue

C · Code with teaching comments

solution.javaJava

Reverse Second Half — O(1) Space (Optimal) — optimal

7 teaching notes

1
public boolean isPalindrome(ListNode head) {
2
    // Empty or single-node lists are trivially palindromes — short-circuit.
3
    if (head == null || head.next == null) {
4
        return true;
5
    }
6
    // 1. find middle (slow ends at start of 2nd half / the middle)
7
    ListNode slow = head, fast = head;
8
    // Fast/slow midpoint; slow lands at the start of the second half (even) or the
9
    // middle (odd).
10
    while (fast != null && fast.next != null) {
11
        slow = slow.next;
12
        fast = fast.next.next;
13
    }
14
    // 2. reverse from slow to the end
15
    // Reverse starting at slow — prev becomes the head of the reversed back half.
16
    ListNode prev = null, curr = slow;
17
    while (curr != null) {
18
        ListNode nxt = curr.next;
19
        curr.next = prev;
20
        prev = curr;
21
        curr = nxt;
22
    }
23
    // 3. compare first half with reversed second half
24
    // left walks the original first half; right walks the reversed second half.
25
    ListNode left = head, right = prev;
26
    boolean ok = true;
27
    // Guard on the reversed half (the shorter side) so the odd middle node is skipped
28
    // harmlessly.
29
    while (right != null) {
30
        // Any mismatched symmetric pair means it's not a palindrome.
31
        if (left.val != right.val) {
32
            ok = false;
33
            break;
34
        }
35
        left = left.next;
36
        right = right.next;
37
    }
38
    // 4. (optional) restore the second half
39
    // Optional restore: reverse the second half again so the caller's list is
40
    // untouched.
41
    ListNode prev2 = null, cur2 = prev;
42
    while (cur2 != null) {
43
        ListNode nxt = cur2.next;
44
        cur2.next = prev2;
45
        prev2 = cur2;
46
        cur2 = nxt;
47
    }
48
    return ok;
49
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.49 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7head = [1, 2, 2, 1] — Even length. slow lands on the 3rd node; reversed back half [1, 2]; compares to [1, 2] → true.Explore edge cases

Edge cases handled

head = [1, 2, 2, 1]Even length. slow lands on the 3rd node; reversed back half [1, 2]; compares to [1, 2] → true.
head = [1, 0, 1]Odd length. Middle 0 pairs with itself; left/right both see [1] before right hits null → true.
head = [1, 2]slow→2, reversed back half [2], compare 1 vs 2 → mismatch → false.

Pitfalls

Looping the comparison while `left != null` instead of `right != null` — overruns on the odd middle and can misread.
Forgetting that the reverse mutates the input; if the list must stay intact, restore it.
Skipping the empty/single-node short-circuit and then dereferencing null in the midpoint loop.
Reversing from head.next or the wrong node instead of slow — misaligns the halves.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong comparison loop guard

Explore the code comparison

Don't write this

left, right = head, prev
while left:            # first half is longer on odd lengths
    if left.val != right.val:
        return False
    left = left.next
    right = right.next  # right becomes None, then .val crashes

Write this instead

left, right = head, prev
while right:           # reversed half is the safe, shorter guard
    if left.val != right.val:
        return False
    left = left.next
    right = right.next

Not restoring a mutated list

The O(1)-space method reverses the back half in place. If the caller still needs the original list (or tests it afterward), leaving it reversed is a silent corruption bug.

Explore the code comparison

Don't write this

# ... compare halves ...
return ok   # list's second half is left reversed

Write this instead

# ... compare halves ...
prev2, cur2 = None, prev
while cur2:
    nxt = cur2.next
    cur2.next = prev2
    prev2 = cur2
    cur2 = nxt
return ok   # original order restored

Crashing the midpoint loop on tiny lists

Without an empty/single-node guard, the same fast.next.next dereference risk applies; and for a clean structure, short-circuiting trivial palindromes is clearer.

Explore the code comparison

Don't write this

ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) { // NPE if head is null
    slow = slow.next;
    fast = fast.next.next;
}

Write this instead

if (head == null || head.next == null) return true;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Fast/slow midpoint + reverse second half + two-pointer compare

Code pattern to memorize

# 1. find middle
slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
# 2. reverse from slow
prev = None
while slow:
    nxt = slow.next; slow.next = prev; prev = slow; slow = nxt
# 3. compare halves
left, right = head, prev
while right:
    if left.val != right.val: return False
    left = left.next; right = right.next
return True

Rules to remember

1Find the middle with fast/slow, then reverse from slow to the end — you compare the first half against the reversed second half.
2Stop the comparison when the second-half (right) pointer hits null; the reversed half is the shorter/equal one, so it's the safe loop guard.
3An odd-length list has a lone middle node that pairs with itself — the right-half walk naturally stops before forcing it to match anything.
4Reversing mutates the input. If the caller must see the original list, reverse the second half back before returning.
5Use fast and fast.next for the midpoint so fast.next.next never dereferences null.
6The array approach is O(n) space but trivially correct — name it as the fallback, then offer the O(1) reverse-half method as the upgrade.

Use this pattern when

Check symmetry of a singly linked list with O(1) extra space
Any problem needing the reversed second half compared against the first (Reorder List shares the split+reverse)
Demonstrating composition of two primitives: midpoint-finding and in-place reversal
When recursion depth (O(n) stack) or an array copy (O(n) space) is unacceptable

Choose another pattern when

Mutating the input is forbidden and you can't restore it → copy values to an array instead
It's a doubly linked list → walk inward from both ends, no reversal needed
Values are huge objects, not cheap ints → comparison cost may dominate; reconsider copying

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Reverse Linked List
The reversal of the second half is exactly this prev/curr/next flip — the core subroutine here.
Middle of the Linked List
The fast/slow split that begins this solution is this problem in isolation.
Reorder List
Same split-then-reverse setup, but interleave the two halves instead of comparing them.
Palindrome Number
Coming soon
Same palindrome idea on an integer's digits — reverse half the number and compare.

Same pattern

←

Middle of the Linked List

Continue · Next problem

Reverse Linked List II