Palindrome Linked List
MediumReverse the back half and walk both
Problem
Given the head of a singly linked list, return true if the sequence of values reads the same forwards and backwards.
Find the middle, reverse the second half, then compare it against the first half node by node.
The idea
Find the middle with slow and fast pointers, reverse everything after it, and compare the two halves node by node. It reads the list twice but allocates nothing.
The trick
- Compare until the reversed half ends — the odd middle node is ignored either way.
- O(n) time, O(1) space.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — head = [1, 2, 2, 1] Values: 1, 2, 2, 1.
1slow=fast=head2while fast and fast.next: slow=slow.next; fast=fast.next.next3second = reverse(slow)4while second: if head.val != second.val: return false; head=head.next; second=second.next5return trueInput
- array
- [1, 2, 2, 1]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- list = 1 -> 2 -> 2 -> 1
- Output:
- true
- Explanation:
- Reads the same both ways.
Example 2
- Input:
- list = 1 -> 2 -> 3
- Output:
- false
- Explanation:
- Backwards it's 3,2,1 → false.
Example 3
- Input:
- list = 7
- Output:
- true
- Explanation:
- Single node is a palindrome.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.