How do you solve Palindrome Linked List?

Use two pointers to find the midpoint. Reverse the second half of the list in-place. Then iterate from the head and from the reversed half simultaneously, comparing values. If all match, return true; otherwise, false. This approach is O(n) time and O(1) space.

What pattern does Palindrome Linked List use?

The Pattern: Fast & Slow Pointers (Midpoint Detection and In-Place Reversal) The Heuristic: Use a fast pointer moving twice as fast as a slow pointer to find the midpoint in a single pass, then reverse the second half in-place to enable direct comparison without extra space.

Palindrome Linked List — Fast & Slow Pointers

Q: What is the time complexity of Palindrome Linked List?

O(n). The list is traversed a constant number of times: once to find the midpoint, once to reverse the second half, and once to compare halves, each O(n).

Problem

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

The number of nodes in the list is in the range [1, 10⁵]
0 ≤ Node.val ≤ 9

Example

Input: head = [1, 2, 2, 1]

Output: true

The algorithm uses two pointers: 'fast' moves two steps at a time, 'slow' moves one step. When 'fast' reaches the end, 'slow' is at the midpoint. For the input [1, 2, 2, 1], 'slow' stops at the second '2'. The second half starting from 'slow' is reversed, resulting in [1, 2]. Then, the algorithm compares nodes from the start and from the reversed second half. Since all corresponding nodes match, it returns true.

Approach

Straightforward Solution

A brute-force approach copies the linked list values into an array and checks if the array is a palindrome. This requires O(n) extra space and two passes.

Core Observation

A palindrome reads the same forwards and backwards. For a singly linked list, this means the first half of the list must match the reversed second half.

Path to Optimal

The key insight is to find the midpoint using fast and slow pointers, reverse the second half in-place, and then compare the two halves node-by-node. This approach uses O(1) extra space and only a few passes over the list.

Optimal Approach

Preview

Use two pointers to find the midpoint. Reverse the second half of the list in-place…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The list is traversed a constant number of times: once to find the midpoint, once to reverse the second half, and once to compare halves, each O(n).

Space

O(1)

Reversing the second half in-place and using pointers for comparison requires only constant extra space, excluding input storage.

Solution

Python

1class Solution:
  def isPalindrome(self, head):
      slow = fast = head
4
      while fast and fast.next:
          slow = slow.next
          fast = fast.next.next
8
      prev = None
      while slow:
          nxt = slow.next
          slow.next = prev
          prev = slow
          slow = nxt
15
      left = head
      right = prev
18
      while right:
          if left.val != right.val:
              return False
          left = left.next
          right = right.next
24
      return True

Step-by-Step Solution

1

Locate the Middle of the Linked List Using Fast and Slow Pointers

3slow = fast = head
5while fast and fast.next:
6    slow = slow.next
7    fast = fast.next.next

Objective

To find the midpoint of the linked list efficiently in a single pass.

Key Insight

Using two pointers moving at different speeds allows detection of the midpoint without knowing the list length upfront. The fast pointer moves two nodes per iteration, the slow pointer moves one. When the fast pointer reaches the end, the slow pointer is at the midpoint, splitting the list into two halves for further processing.

Interview Quick-Check

Core Logic

Fast pointer moves twice as fast as slow pointer, so when fast reaches the end, slow is at midpoint.

State & Boundaries

Loop condition checks both fast and fast.next to avoid null pointer exceptions.

Common Pitfalls & Bugs

Failing to check fast.next can cause runtime errors when fast reaches the last node.

2

Reverse the Second Half of the List In-Place

To reverse the nodes from the midpoint to the end, enabling backward traversal for comparison.

3

Compare the First Half and Reversed Second Half Node-by-Node

To verify if the linked list is a palindrome by comparing corresponding nodes from both halves.

4

Return True if All Node Comparisons Match

To conclude the palindrome check by returning true after successful comparison.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 12 Critical

slow.next = prev

Reverse the current node's next pointer to point to prev.

Redirecting slow.next to prev reverses the link, building the reversed list incrementally.

Line 11 Critical

nxt = slow.next

Save the next node before changing pointers.

Storing slow.next preserves access to the remainder of the list after pointer reversal.

Line 20 Critical

if left.val != right.val:

Check if current node values differ.

A mismatch indicates the list is not a palindrome, allowing early termination.

Full line-by-line criticality + rationale for all 18 lines available on Pro.

Test Your Understanding

Why does reversing the second half of the list enable palindrome checking in O(1) space?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Palindrome Linked List from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Palindrome Linked List drill

or drill a free problem

1	`class Solution:`
2	`def isPalindrome(self, head):`
3	`slow = fast = head`
4
5	`while fast and fast.next:`
6	`slow = slow.next`
7	`fast = fast.next.next`
8
9	`prev = None`
10	`while slow:`
11	`nxt = slow.next`
12	`slow.next = prev`
13	`prev = slow`
14	`slow = nxt`
15
16	`left = head`
17	`right = prev`
18
19	`while right:`
20	`if left.val != right.val:`
21	`return False`
22	`left = left.next`
23	`right = right.next`
24
25	`return True`

3	`slow = fast = head`
5	`while fast and fast.next:`
6	`slow = slow.next`
7	`fast = fast.next.next`