Palindrome Linked List

Given the head of a singly linked list, return true if the list reads the same forwards and backwards — a palindrome — and false otherwise.

A singly linked list only lets you walk forward: from any node you can reach node.next, but never the node before it. So the whole challenge is checking a back-to-front property using a structure that only moves front-to-back.

For example, 1 → 2 → 2 → 1 is a palindrome (the sequence [1,2,2,1] mirrors itself), while 1 → 2 is not.

Hints

· Stuck? Reveal one nudge at a time.

A palindrome reads the same both ways — but a singly linked list only lets you read one way. What could you do so the values become readable from both ends?

If you had the values in an array, the check is a trivial two-pointer sweep from the ends inward. Is there a way to avoid the extra array?

Find the middle with slow/fast pointers, reverse the second half in place, then walk the two halves toward each other comparing values.

Common doubts

Yes. The middle node has no mirror partner, and gating the compare loop on the (shorter) reversed half naturally skips it.

Yes — any list of length 0 or 1 reads the same forwards and backwards, so it returns true.

Interview follow-ups

· What an interviewer asks next.

Yes — that is exactly the optimal approach: slow/fast to find the middle, reverse the second half in place, then compare the two halves without any extra array.

After comparing, reverse the second half a second time to restore the original next pointers before returning — still O(1) extra space.

Fun facts

The slow/fast pointer pair used to find the middle here is the same 'tortoise and hare' idea that detects cycles in a linked list — one technique, many problems.
Reversing a portion of a list in place is a building block that reappears in problems like reversing nodes in k-groups and reordering a list.

Asked at

AmazonMicrosoftGoogleAdobeMeta

Frequently Sometimes Occasionally

Example 1

Input: head = [1,2,2,1]
Output: true
Reading the values forward gives [1,2,2,1]; backward gives [1,2,2,1] — identical.

Example 2

Input: head = [1,2]
Output: false
Forward is [1,2], backward is [2,1] — they differ, so it is not a palindrome.

Constraints

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

A palindrome check is trivial on an array — compare the two ends and walk inward. On a singly linked list you have no way to walk inward from the back, and that single restriction is the whole puzzle. We'll build up from the obvious copy-to-array approach to an elegant O(1)-space trick.

Prerequisites

Before you start

· Concepts used directly in the solution.

Singly linked list traversal. You can only move forward via node.next; there is no pointer back to the previous node.

Two-pointer (slow/fast). Advancing one pointer by 1 and another by 2 lands the slow pointer on the middle when the fast one reaches the end.

In-place list reversal. Re-pointing each next to the previous node reverses a list without extra memory.

Understand the problem

Restated plainly: collect the node values in order and ask whether that sequence equals its own reverse. Formally, with values v[0..n-1], the list is a palindrome iff v[i] == v[n-1-i] for every i.

Worked example — head = [1,2,3,2,1]

1 → 2 → 3 → 2 → 1
^                ^   v[0]=1, v[4]=1  ✓
     ^      ^        v[1]=2, v[3]=2  ✓
          ^          v[2]=3  (middle, ignored)
all mirrored pairs match → true

Clarifying questions

Stating what you'll confirm before coding shows you think about inputs, not just algorithms — exactly what an interviewer is grading.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Is the list guaranteed to have at least one node?”

A single node is always a palindrome; an empty list is a vacuous edge case worth confirming.

Edge cases

“Can I mutate the list, or must its structure be preserved?”

The optimal approach reverses half the list; if the caller reuses it afterward you should restore it.

Constraints and scale

“How large can the list get?”

With up to 10^5 nodes, a quadratic compare is fine but the copy-to-array space may matter — it steers brute force vs the O(1) trick.

The ideal opening — say it like this

Before I start, I have a couple of quick clarifying questions.

First — can I assume at least one node, and how large can the list get?

And finally — am I allowed to modify the list in place, or should I leave it untouched when I'm done?

Key observations

1Aha

A palindrome check only needs the two halves, mirrored

The first half compared front-to-back must match the second half compared back-to-front. The middle node (for odd length) never needs comparing — it mirrors itself.

2Aha

Slow/fast finds the middle in one pass

Move slow by one and fast by two. When fast falls off the end, slow sits at the midpoint — no length count required.

1 → 2 → 3 → 2 → 1
s   f
    s        f
         s        f=null → slow at 3 (middle)

3Aha

Reversing the second half makes both halves walkable forward

Once the back half points the other way, you have two forward-walkable chains — one from head, one from the new tail — and comparing them node-by-node needs no extra array.

Brute force vs optimal

	Copy to array	Reverse half in place
Time	O(n)	O(n)
Space	O(n)	O(1)
Mutates list		Yes (restorable)

Both run in linear time; the optimal one trades a little pointer juggling for constant extra space. See the full code for each in the Approaches selector below.

Summary

Key takeaway

When a structure only moves one way but you need a two-ended check, either materialize it (copy to an array) or make the far end walkable (reverse half in place). The slow/fast + reverse combo is the canonical O(1)-space pattern for linked-list symmetry.

slow, fast = head, head
while fast and fast.next: slow = slow.next; fast = fast.next.next
second = reverse(slow)
while second: if head.val != second.val: return false; advance both
return true