Log inSign up
easyLeetCodeNot Started

Palindrome Linked List

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

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

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

Example 1 · Even Palindrome:

Input: head = [1,2,2,1]
Output: true
Explanation: Reads the same forwards and backwards: 1 -> 2 -> 2 -> 1.

Example 2 · Non-Palindrome:

Input: head = [1,2]
Output: false
Explanation: 1 -> 2 does not equal 2 -> 1.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Combine Fast/Slow midpoint finding with in-place pointer reversal.
  • Perform symmetric two-pointer comparisons on singly linked structures.
  • Restore mutated data structures back to their original state in production code.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Symmetric sequence validation on unidirectional pointer structures.
  • O(1) memory follow-up prohibiting stacks, arrays, or deep recursion.
  • Combination of two core primitives: Finding Middle + In-Place Reversal.

Algorithmic Decision Tree:

  • If extra memory is allowed, copy values to an array and use standard two-pointer array palindrome checking.
  • For optimal O(1) space, split at midpoint with fast/slow, reverse second half, and compare.

Connected Patterns:

Reverse Linked ListMiddle of the Linked ListReorder ListValid Palindrome

1. Brute Force — Copy to Array & Two-Pointer Validation

Intuition

Convert the linked list into an array. Check if the array is a palindrome using two pointers moving toward the center.

Algorithm

  1. Step 1: Traverse list and copy each node's val into array vals.
  2. Step 2: Initialize left = 0, right = vals.length - 1.
  3. Step 3: While left < right:
  4. a. If vals[left] != vals[right], return false.
  5. b. left++, right--.
  6. Step 4: Return true.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6struct ListNode {
7 int val;
8 ListNode *next;
9 ListNode(int x) : val(x), next(nullptr) {}
10};
11
12class Solution {
13public:
14 bool isPalindrome(ListNode* head) {
15 vector<int> vals;
16 for (ListNode* c = head; c; c = c->next) {
17 vals.push_back(c->val);
18 }
19
20 int left = 0, right = (int)vals.size() - 1;
21 while (left < right) {
22 if (vals[left] != vals[right]) return false;
23 left++;
24 right--;
25 }
26 return true;
27 }
28};
29
30int main() {
31 ListNode* h = new ListNode(1);
32 h->next = new ListNode(2);
33 h->next->next = new ListNode(2);
34 h->next->next->next = new ListNode(1);
35
36 Solution sol;
37 cout << "Brute Force isPalindrome: " << (sol.isPalindrome(h) ? "true" : "false") << endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N) — Traverses the linked list of N nodes in O(N) and compares array elements in O(N/2).
  • Space complexity: O(N) — Allocates an array buffer of size N.

Why Brute Force Doesn't Scale:

Array conversion allocates O(N) memory, which for N = 105 uses ~1MB and triggers heap allocations.

For N = 100,000, in-place palindrome validation runs in <1.2ms with 0 extra heap memory.

2. Better — Recursive Unwinding Call Stack Comparison

Intuition

Maintain frontPointer = head. Dive recursively to the end of the list. When the recursive helper reaches the tail, compare the tail value with frontPointer.val and advance frontPointer = frontPointer.next. As the stack unwinds, comparisons move from the outside inward.

Algorithm

  1. Step 1: Set global / closure front = head.
  2. Step 2: Define recursive helper check(node):
  3. a. If node == null, return true.
  4. b. If !check(node.next), return false.
  5. c. If front.val != node.val, return false.
  6. d. front = front.next.
  7. e. Return true.
  8. Step 3: Return check(head).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode(int x) : val(x), next(nullptr) {}
9};
10
11class Solution {
12 ListNode* front;
13 bool check(ListNode* curr) {
14 if (!curr) return true;
15 if (!check(curr->next)) return false;
16 if (front->val != curr->val) return false;
17 front = front->next;
18 return true;
19 }
20public:
21 bool isPalindrome(ListNode* head) {
22 front = head;
23 return check(head);
24 }
25};
26
27int main() {
28 ListNode* h = new ListNode(1);
29 h->next = new ListNode(2);
30 h->next->next = new ListNode(2);
31 h->next->next->next = new ListNode(1);
32
33 Solution sol;
34 cout << "Recursive isPalindrome: " << (sol.isPalindrome(h) ? "true" : "false") << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(N) — Recursion traverses N nodes down to the tail and compares on N unwinding steps.
  • Space complexity: O(N) call stack — Recursive call stack holds N activation records.

3. Optimal — Fast/Slow Midpoint + Second Half In-Place Reversal

Intuition

Use slow and fast (starting fast = head.next) to locate the end of the first half. Reverse the second half in place starting at slow.next. Compare p1 = head and p2 = reversedSecondHalfHead. Restore the second half by reversing it again, and return the result.

Algorithm

  1. Step 1: If head == null || head.next == null, return true.
  2. Step 2: Find midpoint: slow = head, fast = head.next; while fast != null && fast.next != null: slow = slow.next, fast = fast.next.next.
  3. Step 3: Reverse second half: secondHalf = reverse(slow.next).
  4. Step 4: Compare halves: p1 = head, p2 = secondHalf, isPalin = true; while p2 != null: if p1.val != p2.val: isPalin = false; break; p1 = p1.next, p2 = p2.next.
  5. Step 5: Restore second half: slow.next = reverse(secondHalf).
  6. Step 6: Return isPalin.

Palindrome Linked List Master Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Second half begins at node 2b
Visual state
Values and pointers at this exact step
linked list
slow → 2a
Node 1a
1
Node 2a
2
Node 2b
2
Node 1b
1
NULL
Check / comparison
Midpoint found
Decision / next transition
Reverse slow.next
Why this step matters

Second half begins at node 2b.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode(int x) : val(x), next(nullptr) {}
9};
10
11class Solution {
12 ListNode* reverseList(ListNode* head) {
13 ListNode* prev = nullptr;
14 ListNode* curr = head;
15 while (curr) {
16 ListNode* nextTemp = curr->next;
17 curr->next = prev;
18 prev = curr;
19 curr = nextTemp;
20 }
21 return prev;
22 }
23public:
24 bool isPalindrome(ListNode* head) {
25 if (!head || !head->next) return true;
26
27 // 1. Find end of first half
28 ListNode* slow = head;
29 ListNode* fast = head->next;
30 while (fast && fast->next) {
31 slow = slow->next;
32 fast = fast->next->next;
33 }
34
35 // 2. Reverse second half
36 ListNode* secondHalf = reverseList(slow->next);
37
38 // 3. Compare halves
39 ListNode* p1 = head;
40 ListNode* p2 = secondHalf;
41 bool isPalin = true;
42 while (p2 != nullptr) {
43 if (p1->val != p2->val) {
44 isPalin = false;
45 break;
46 }
47 p1 = p1->next;
48 p2 = p2->next;
49 }
50
51 // 4. Restore list
52 slow->next = reverseList(secondHalf);
53
54 return isPalin;
55 }
56};
57
58int main() {
59 ListNode* h = new ListNode(1);
60 h->next = new ListNode(2);
61 h->next->next = new ListNode(2);
62 h->next->next->next = new ListNode(1);
63
64 Solution sol;
65 cout << "Optimal isPalindrome: " << (sol.isPalindrome(h) ? "true" : "false") << endl;
66 return 0;
67}

Time & Space Complexity

  • Time complexity: O(N) — Finding midpoint takes N/2 steps. Reversing second half takes N/2 steps. Comparison takes N/2 steps. Restoring list takes N/2 steps. Total operations <= 2N in strictly O(N) time.
  • Space complexity: O(1) — Operates strictly in-place with O(1) auxiliary pointer variables.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Copy Values to Dynamic ArrayO(N)O(N)Traverse the list and push all node values into an array/vector. Use two pointers left = 0 and right = arr.length - 1 moving inward to verify symmetry.Memory allocation for array buffer.
2.Better — Recursive Call Stack ComparisonO(N)O(N) recursion stackMaintain a pointer front = head. Recursively dive to the tail of the list. On the unwinding phase, compare front.val with current.val and advance front = front.next.Call stack frames.
3.Optimal — Midpoint Split & In-Place Second Half ReversalOptimalO(N)O(1)1. Find middle with fast/slow pointers. 2. Reverse second half in place. 3. Compare first and second half values. 4. Restore second half. 5. Return result.Optimal.

Common Pitfalls & Crucial Edge Cases

Not restoring the linked list

In interviews, failing to mention or execute restoring the second half leaves a mutated list with disconnected nodes.

Initializing fast pointer incorrectly

Starting fast = head for an even list lands slow on the second middle (index 2), which cuts the first half too long.

Looping until `p1 != null` instead of `p2 != null`

The first half might be one node longer than the second half on odd-length lists, so the comparison loop must be bound by p2 != null.

Crucial Edge Cases to Validate:

  • Single Node — head = [1] -> returns true.
  • Two Nodes Equal — head = [1, 1] -> true.
  • Two Nodes Unequal — head = [1, 2] -> false.
  • Odd Length Palindrome — head = [1, 2, 3, 2, 1] -> slow lands on 3, slow.next [2, 1] reversed to [1, 2], matches [1, 2] -> true.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Outline the 4 steps clearly: '1. Fast/slow midpoint. 2. Reverse second half. 3. Compare halves. 4. Restore list.'
  2. Emphasize the follow-up O(1) space constraint without using arrays or recursion.
  3. Show attention to production quality by explicitly restoring slow.next = reverse(secondHalf) before returning.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why should the comparison loop terminate when p2 == null instead of p1 == null?

2.Why is restoring the linked list important in production applications?

3.What is the auxiliary space complexity of the optimal in-place algorithm?

Back to DSA Sheet