← DSA Atlas
Dedicated problem page · #234

Palindrome Linked List

EasyLinked Lists and Pointer ManipulationFind middle, reverse half, compareSlow/fast pointers with in-place reversal
Solve on LeetCode ↗
234
EasyLinked Lists and Pointer ManipulationSlow/fast pointers with in-place reversalFind middle, reverse half, compare

Palindrome Linked List

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

Open official problem prompt ↗
In plain English

Decide whether the values along a singly linked list form a palindrome, ideally without allocating extra memory proportional to the list length.

Picture it like this

Folding a strip of paper in half: if every letter on the top half lines up with the letter beneath it, the word reads the same both ways.

Example
Input
head = [1,2,2,1]
Output
true
Why
Reading the values forward gives 1,2,2,1 and backward gives 1,2,2,1, which are identical.
Constraints
The number of nodes is in the range [1, 10^5]0 <= Node.val <= 9Follow up: solve in O(n) time and O(1) space
Pattern lesson

See the pattern, then code

Find middle, reverse half, compare
Recognition clue

A palindrome check on a singly linked list where you cannot walk backwards, combined with a follow-up demanding O(1) space, signals the find-middle-then-reverse-half technique rather than copying values into an array.

↗
Linked Lists and Pointer Manipulation

Reversal, cycle detection, merging, reordering, or O(1)-space sequence edits.. If you reverse the second half of the list in place, its nodes now point back toward the middle, so you can compare the first half against the reversed second half node by node. A palindrome matches on every step.

New words, made simpleKnow these before the algorithm
Palindrome
A sequence that is identical when read forward and backward.
In-place reversal
Flipping the direction of a list's pointers using only a few temporary variables.
Two-pointer convergence
Walking two pointers from opposite ends toward the center and comparing as they go.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Copy values to array

Trivially correct but uses linear extra space, failing the O(1) follow-up.

Push every value into a list and check if it equals its reverse.

Time O(n)Space O(n)
Best choiceMiddle + reverse second half

Meets both time and space targets with only pointer rewiring.

Find the midpoint, reverse the back half in place, then compare the two halves node by node.

Time O(n)Space O(1)
The rule we keep true

Invariant

After the split, left starts at the head and right starts at the reversed tail; at each comparison the two pointers are equidistant from the center, so matching values means the outer pair is symmetric.

Why this is correct

Reasoning

Reversing the second half makes its traversal order the mirror of the original back-to-front order. Comparing the first half against it therefore compares position i against position n-1-i. If all such pairs match, the list is a palindrome. Stopping when right is exhausted correctly ignores the lone middle node in odd-length lists.

The algorithm in three movesSay these aloud before coding
1Use slow/fast pointers to reach the middle

slow stops at index 2

2Reverse the second half in place starting from slow

reversed 2nd half: 1 -> 2

3Walk the first half and reversed second half together, comparing values

compare 1=1, 2=2 -> true

4Return false on any mismatch, otherwise true

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
21
22
13
1 · Read[1,2,2,1]
2 · AskWhere does slow stop?
3 · Update stateslow at 3rd node (value 2)
4 · ResultSecond half begins at value 2 (index 2)
Key takeaway

Comparing the front half against the reversed back half from both ends inward.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-6Locate the middle

    When fast reaches the end, slow sits at the start of the second half (for odd length, just past the true center).

  2. 2
    Lines 7-12Reverse the second half

    Standard three-pointer reversal turns the back half around so prev heads it.

  3. 3
    Lines 13-19Compare halves

    Walk left from the head and right from the reversed tail; any value mismatch means it is not a palindrome. The loop ends when right runs out, naturally skipping the odd middle node.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single node (always a palindrome)
  • Two equal nodes [1,1] returns true
  • Two different nodes [1,2] returns false
  • Odd length where the middle node is ignored
  • All identical values
!

Common beginner mistakes

  • Looping while left AND right and using left as the guard can over-run on odd lengths; guard on right only
  • Forgetting that this mutates the list (the second half stays reversed); restore it if the caller reuses the list
  • Off-by-one in midpoint selection so the halves overlap or leave a node uncompared
Check your understanding

Why does looping while `right` (not `left`) correctly handle odd-length lists?

More in Linked Lists and Pointer Manipulation

#206Reverse Linked ListIterative pointer reversal#141Linked List CycleFast and slow pointers (Floyd's cycle detection)#143Reorder ListFind middle, reverse second half, merge alternately#138Copy List with Random PointerClone with old-to-new node mapping#146LRU CacheHash map plus recency-ordered structure#2Add Two NumbersDigit-by-digit addition with carry