LeetCode 234 - Palindrome Linked List

The problem gives us the head of a singly linked list and asks whether the sequence of values stored in the list forms a palindrome. A palindrome is a sequence that reads the same forward and backward.

leetcodeeasylinked-listtwo-pointersstackrecursion

LeetCode Problem 234

Difficulty: 🟢 Easy
Topics: Linked List, Two Pointers, Stack, Recursion

Solution

Problem Understanding

The problem gives us the head of a singly linked list and asks whether the sequence of values stored in the list forms a palindrome.

A palindrome is a sequence that reads the same forward and backward. For example, the array [1,2,2,1] is a palindrome because reversing it produces the same sequence. On the other hand, [1,2] is not a palindrome because the forward and backward orders differ.

The input is a singly linked list, which means each node contains a value and a pointer to the next node. Unlike arrays, linked lists do not support direct indexing, so we cannot easily compare elements from both ends simultaneously unless we use additional techniques.

The expected output is:

  • true if the linked list values form a palindrome
  • false otherwise

The constraints are important:

  • The list contains between 1 and 10^5 nodes
  • Each node value is between 0 and 9

The large upper bound means we should avoid unnecessarily expensive operations. An O(n^2) approach could become too slow for large inputs. The follow-up question specifically asks whether we can solve the problem in O(n) time and O(1) extra space, which strongly suggests that the intended solution should avoid auxiliary data structures proportional to the input size.

Several edge cases are important:

  • A single-node list is always a palindrome
  • A two-node list may or may not be a palindrome
  • Odd-length lists have a middle element that does not need comparison
  • Even-length lists split evenly into two comparable halves
  • Since the list is singly linked, traversing backward is impossible without reversing part of the structure or using extra memory

Understanding how to efficiently compare the first half and second half of the list is the key challenge of this problem.

Approaches

Brute Force Approach

The most straightforward solution is to copy all linked list values into an array. Once the values are stored in an array, checking whether the sequence is a palindrome becomes trivial because arrays support random access.

We traverse the linked list once, append every node value into a list, and then use two pointers:

  • One pointer starts at the beginning
  • The other starts at the end

We repeatedly compare values while moving inward. If all corresponding values match, the sequence is a palindrome.

This approach is correct because the array preserves the exact order of the linked list values. Comparing mirrored positions directly verifies whether the sequence reads identically forward and backward.

However, this approach uses O(n) extra space because we store every node value separately. The follow-up explicitly asks whether we can do better.

Optimal Approach

The key insight is that we do not actually need to store the entire list. Instead, we can reverse only the second half of the linked list in place.

The algorithm works as follows:

  • Use fast and slow pointers to find the middle of the list
  • Reverse the second half of the linked list
  • Compare the first half and reversed second half node by node
  • If all values match, the list is a palindrome

This works because reversing the second half allows us to traverse both halves in the same direction while comparing mirrored elements.

The fast and slow pointer technique is especially useful because:

  • The slow pointer advances one step at a time
  • The fast pointer advances two steps at a time
  • When the fast pointer reaches the end, the slow pointer is at the middle

This gives us an O(n) time solution with only O(1) extra space because the reversal is done in place.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Copy values into an array and compare from both ends
Optimal O(n) O(1) Reverse second half of the linked list in place

Algorithm Walkthrough

  1. Initialize two pointers, slow and fast, both starting at the head of the list.

The purpose of these pointers is to locate the middle efficiently. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time. 2. Move the pointers until fast reaches the end.

At the end of this process:

  • If the list length is odd, slow lands on the middle node
  • If the list length is even, slow lands at the start of the second half

This works because the fast pointer covers distance twice as quickly. 3. Reverse the second half of the linked list starting from slow.

Reversing is necessary because singly linked lists only allow forward traversal. By reversing the second half, we can compare mirrored elements sequentially.

During reversal:

  • Maintain prev, current, and next_node
  • Redirect each node's next pointer backward
  • Continue until the entire half is reversed
  1. Compare the first half and reversed second half.

Use two pointers:

  • One starting at the original head
  • One starting at the head of the reversed half

Compare node values one by one.

If any pair differs, return False immediately. 5. If all comparisons succeed, return True.

Every mirrored pair matched, so the linked list is a palindrome.

Why it works

The algorithm works because reversing the second half transforms the palindrome comparison into a synchronized forward traversal.

For a palindrome:

  • The first node must equal the last node
  • The second node must equal the second-to-last node
  • And so on

Reversing the second half places these mirrored nodes in the same traversal direction, allowing direct comparison in linear time. Since every node is visited only a constant number of times, the algorithm remains efficient.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from typing import Optional

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head

        # Find the middle of the list
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # Reverse the second half
        prev = None
        current = slow

        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node

        # Compare both halves
        left = head
        right = prev

        while right:
            if left.val != right.val:
                return False

            left = left.next
            right = right.next

        return True

The implementation begins by locating the midpoint using the fast and slow pointer technique. This avoids needing to count the length separately.

Next, the code reverses the second half in place. The prev pointer tracks the already reversed portion, while current iterates through the remaining nodes. Each node's next pointer is redirected backward.

After reversal, the list is effectively split into two forward-traversable halves:

  • The original first half
  • The reversed second half

The final comparison loop walks through both halves simultaneously. Since the reversed second half represents the mirrored order of the original list, matching values confirm the palindrome property.

The comparison loop only needs to iterate through the second half because its length is never greater than the first half.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    slow := head
    fast := head

    // Find middle
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    // Reverse second half
    var prev *ListNode
    current := slow

    for current != nil {
        nextNode := current.Next
        current.Next = prev
        prev = current
        current = nextNode
    }

    // Compare halves
    left := head
    right := prev

    for right != nil {
        if left.Val != right.Val {
            return false
        }

        left = left.Next
        right = right.Next
    }

    return true
}

The Go implementation follows the exact same algorithmic structure as the Python version.

The primary language-specific difference is pointer handling. Go uses explicit nil checks and pointer types such as *ListNode. Variable declarations are also more explicit in Go, especially for pointer initialization during reversal.

Since node values are small integers, integer overflow is not a concern in either language.

Worked Examples

Example 1

Input:

[1,2,2,1]

Initial list:

1 -> 2 -> 2 -> 1

Step 1: Find the Middle

Iteration slow fast
Start 1 1
1 2 2
2 2 null

The slow pointer is now at the beginning of the second half.

Step 2: Reverse Second Half

Original second half:

2 -> 1

Reversed second half:

1 -> 2

Step 3: Compare Halves

Left Pointer Right Pointer Match
1 1 Yes
2 2 Yes

All values match, so the result is:

true

Example 2

Input:

[1,2]

Initial list:

1 -> 2

Step 1: Find the Middle

Iteration slow fast
Start 1 1
1 2 null

Step 2: Reverse Second Half

Second half:

2

Reversed second half remains:

2

Step 3: Compare Halves

Left Pointer Right Pointer Match
1 2 No

Mismatch found immediately, so the result is:

false

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited a constant number of times
Space O(1) Reversal is performed in place without extra storage

The algorithm performs three linear passes:

  • Finding the middle
  • Reversing the second half
  • Comparing both halves

Each pass touches at most n nodes, so the total time complexity remains linear.

The space complexity is constant because no auxiliary data structure proportional to the input size is used. Only a few pointer variables are maintained throughout execution.

Test Cases

# Helper utilities for testing

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode()
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

solution = Solution()

# Provided examples
assert solution.isPalindrome(build_list([1, 2, 2, 1])) == True   # even-length palindrome
assert solution.isPalindrome(build_list([1, 2])) == False         # simple non-palindrome

# Single node
assert solution.isPalindrome(build_list([1])) == True             # single element

# Odd-length palindrome
assert solution.isPalindrome(build_list([1, 2, 3, 2, 1])) == True

# Odd-length non-palindrome
assert solution.isPalindrome(build_list([1, 2, 3, 4, 5])) == False

# Even-length palindrome
assert solution.isPalindrome(build_list([4, 5, 5, 4])) == True

# Even-length non-palindrome
assert solution.isPalindrome(build_list([1, 2, 3, 4])) == False

# Repeated values
assert solution.isPalindrome(build_list([7, 7, 7, 7])) == True

# Near palindrome with one mismatch
assert solution.isPalindrome(build_list([1, 2, 3, 2, 2])) == False

# Large symmetric structure
assert solution.isPalindrome(build_list([1,2,3,4,3,2,1])) == True
Test Why
[1,2,2,1] Standard even-length palindrome
[1,2] Smallest non-palindrome
[1] Single-node edge case
[1,2,3,2,1] Odd-length palindrome
[1,2,3,4,5] Odd-length non-palindrome
[4,5,5,4] Even-length palindrome
[1,2,3,4] Even-length non-palindrome
[7,7,7,7] Identical repeated values
[1,2,3,2,2] Near-palindrome mismatch
[1,2,3,4,3,2,1] Larger symmetric structure

Edge Cases

Single-Node List

A linked list containing only one node is always a palindrome because reading it forward and backward produces the same sequence.

This case can sometimes cause pointer-related bugs if the implementation assumes the existence of multiple nodes. In this solution, the fast and slow pointer loop exits immediately, and the comparison phase succeeds naturally.

Odd-Length Lists

Odd-length palindromes contain a middle element with no mirrored counterpart. For example:

1 -> 2 -> 3 -> 2 -> 1

The value 3 in the middle does not need comparison.

A common mistake is incorrectly handling the midpoint, causing comparisons to become misaligned. This implementation avoids the issue because the reversal starts at slow, and the comparison loop only traverses the reversed second half.

Even-Length Lists

Even-length lists split cleanly into two equal halves:

1 -> 2 -> 2 -> 1

There is no single middle node.

Incorrect midpoint calculations can easily skip nodes or compare mismatched pairs. The fast and slow pointer strategy correctly positions slow at the start of the second half, ensuring proper reversal and comparison.

Non-Palindrome With Early Mismatch

Lists such as:

1 -> 2

should terminate quickly once a mismatch is detected.

The implementation immediately returns False during comparison instead of continuing unnecessary traversal, which improves efficiency while maintaining correctness.