DSA Tracker

Visualize

Palindrome Linked List

A palindrome reads identically forwards and backwards, but a singly-linked list can only be walked forward — there's no way to compare node i against node n-1-i without first turning the back half around. So physically reverse the second half in place (no extra array needed), then walk two pointers outward from the split comparing values one by one; any mismatch means it isn't a palindrome. Finding the middle first with slow/fast pointers means the length never has to be known in advance.

Details

Animated on: Check if list [1,2,2,1] is a palindrome: middle at idx1, reverse second half [2,1]→[1,2], compare [1,2] vs [1,2] → true

Problem:Palindrome Linked ListEasy

Pattern:Fast and Slow Pointers

Linked List

step 1 / 8

1
[0]
2
[1]
2
[2]
1
[3]

Input: list [1,2,2,1] (even length, palindrome). Slow/fast pointers start at head (idx0). Slow moves 1 step, fast moves 2 steps per iteration to find the middle.

  • slow=0· arr[0] = 1
  • fast=0· arr[0] = 1
Pseudocode
1FUNCTION isPalindrome(head):
2  IF the list is empty or has one node: RETURN true
3  slow = head; fast = head
4  WHILE fast can still take two steps: move slow one forward; move fast two forward
5  second = reverse(the node after slow)   (reverse the back half)
6  first = head
7  WHILE second still has nodes: IF first's value is not equal to second's value RETURN false; move first forward; move second forward
8  RETURN true
9END FUNCTION
10FUNCTION reverse(head): prev = nothing; curr = head; WHILE curr has nodes: next = node after curr; point curr back to prev; prev = curr; curr = next; RETURN prev

← / → step · space play · Home restart

Every step in words

Show all 8 steps
  1. Input: list [1,2,2,1] (even length, palindrome). Slow/fast pointers start at head (idx0). Slow moves 1 step, fast moves 2 steps per iteration to find the middle.
  2. while (fast.next && fast.next.next): Iteration 1. slow advances to idx1(val2), fast advances 2 steps: idx0→idx1→idx2. Now slow=idx1 (middle), fast=idx2 (last node).
  3. Second iteration check: fast.next=idx3(val1) exists, fast.next.next=null (past end). Loop exits. slow is at idx1, the start of the second half. Second half to reverse: slow.next = idx3, value 1.
  4. Reverse second half: slow.next (idx3=value1) becomes new head. Reverse list: idx3(val1)→idx2(val2)→idx1(val2)→idx0(val1). After reverse: second half becomes [1,2] (reversed from original [2,1]).
  5. Second half reversed: original second half [2,1] reversed to [1,2]. Now compare first half [1,2] with reversed second half [1,2] value-by-value.
  6. Compare step 1: first[idx0]=1 vs second[idx0]=1. Values match! Both are 1. first moves to idx1, second moves to idx1.
  7. Compare step 2: first[idx1]=2 vs second[idx1]=2. Values match! Both are 2. first moves past end, second moves past end. All comparisons complete.
  8. Return true: [1,2,2,1] is a palindrome. Both halves match value-by-value: 1===1 and 2===2. The list reads the same forward and backward.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Palindrome Linked List in the editorAll Linked List problemsBack to roadmap