LeetCode 234: Palindrome Linked List Solution in Python – A Step-by-Step Guide

Imagine checking if a linked list reads the same forwards and backwards, like a palindrome word—that’s the essence of LeetCode 234: Palindrome Linked List! This easy-level problem challenges you to determine if a singly linked list is a palindrome, meaning its sequence of values mirrors itself. Using Python, we’ll explore two solutions: the Best Solution (a two-pointer with reversal approach) for its space efficiency, and an Alternative Solution (a stack-based approach) for its straightforward simplicity. With beginner-friendly breakdowns, detailed examples, and clear code, this guide will help you master linked list palindromes and sharpen your coding skills. Let’s check that list!

What Is LeetCode 234: Palindrome Linked List?

In LeetCode 234: Palindrome Linked List, you’re given the head of a singly linked list, and your task is to return True if the list is a palindrome (e.g., 1->2->2->1) and False otherwise (e.g., 1->2->3). A palindrome list has values that are symmetric around its center. This differs from digit-counting tasks like LeetCode 233: Number of Digit One, focusing instead on linked list traversal and comparison.

Problem Statement

Input: Head of a singly linked list.
Output: Boolean—True if palindrome, False otherwise.
Rules: Check symmetry in O(n) time, ideally O(1) space.

Constraints

Number of nodes: 1 to 10^5.
Node values: 0 to 9.

Examples

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

Output: True (1->2->2->1 is symmetric).

Input: head = [1,2]

Output: False (1->2 is not symmetric).

Input: head = [1]

Output: True (single node is a palindrome).

Understanding the Problem: Checking Palindromes

To solve LeetCode 234: Palindrome Linked List in Python, we need to verify if the list’s values read the same forward and backward. This isn’t about queue implementation like LeetCode 232: Implement Queue using Stacks—it’s about linked list manipulation. Since it’s singly linked, we can’t traverse backward naturally, so we need a strategy to compare ends. We’ll explore two approaches: 1. Best Solution (Two-Pointer with Reversal): O(n) time, O(1) space—efficient and in-place. 2. Alternative Solution (Stack-Based): O(n) time, O(n) space—simple but space-heavy.

Let’s start with the best solution.

Best Solution: Two-Pointer with Reversal Approach

Why This Is the Best Solution

The two-pointer with reversal approach is our top choice for LeetCode 234 because it achieves O(1) space complexity by reversing the second half of the list in-place, then comparing it with the first half. It’s efficient, clever, and meets the problem’s ideal constraints, making it perfect for linked list enthusiasts.

How It Works

Use two pointers (slow and fast) to find the middle of the list.
Reverse the second half of the list.
Compare the first half (from head) with the reversed second half.
Restore the list (optional, not required by problem).

Step-by-Step Example

Example 1: [1,2,2,1]

List: 1->2->2->1
Find Middle:

Slow = 1, Fast = 1.
Slow = 2, Fast = 2.
Slow = 2 (second), Fast = null (end).
Middle: Second 2.

Reverse Second Half:

Before: 2->1
After: 1->2
List becomes: 1->2->1->2

Compare:

First half: 1->2
Second half: 1->2
1 vs 1, 2 vs 2 → All match.

Output: True.

Example 2: [1,2]

List: 1->2
Find Middle: Slow = 2, Fast = null.
Reverse: 2 (single node, no change).
Compare: 1 vs 2 → No match.
Output: False.

Code with Detailed Line-by-Line Explanation

Here’s the Python implementation:

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

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        # Line 1: Handle empty or single node
        if not head or not head.next:
            return True

        # Line 2: Find middle with slow and fast pointers
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # Line 3: Reverse second half
        prev = None
        curr = slow
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node

        # Line 4: Compare first and second halves
        first = head
        second = prev
        while second:  # Second half might be shorter
            if first.val != second.val:
                return False
            first = first.next
            second = second.next

        # Line 5: Return result
        return True

Time Complexity: O(n) – three passes (middle, reverse, compare).
Space Complexity: O(1) – only pointers used.

Alternative Solution: Stack-Based Approach

Why an Alternative Approach?

The stack-based approach stores the list’s values in a stack, then compares them as they’re popped against the list from the start. It’s a great alternative if you prefer a simpler logic flow or don’t mind extra space, offering a clear way to check symmetry.

How It Works

Push all node values onto a stack.
Traverse the list again, comparing each value with the stack’s top (popping as you go).
If all match, it’s a palindrome.

Step-by-Step Example

Example: [1,2,2,1]

Stack: Push 1, 2, 2, 1 → [1,2,2,1].
Compare:

1 vs pop(1): Match.
2 vs pop(2): Match.
2 vs pop(2): Match.
1 vs pop(1): Match.

Output: True.

Example: [1,2]

Stack: [1,2].
Compare: 1 vs 2, no match.
Output: False.

Code for Stack-Based Approach

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

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        # Line 1: Handle edge cases
        if not head or not head.next:
            return True

        # Line 2: Store values in stack
        stack = []
        curr = head
        while curr:
            stack.append(curr.val)
            curr = curr.next

        # Line 3: Compare with stack
        curr = head
        while curr:
            if curr.val != stack.pop():
                return False
            curr = curr.next

        # Line 4: Return result
        return True

Time Complexity: O(n) – two passes (store and compare).
Space Complexity: O(n) – stack stores all values.

Comparing the Two Solutions

Best Solution (Two-Pointer with Reversal):

Pros: O(1) space, in-place reversal.
Cons: More complex with pointers and reversal.

Alternative Solution (Stack-Based):

Pros: Simple logic, easy to understand.
Cons: O(n) space.

The two-pointer reversal method is our best for its space efficiency.

Additional Examples and Edge Cases

Single Node

Input: [1]
Output: True (symmetric).

Odd Length

Input: [1,2,1]
Middle: 2, compare 1 vs 1 → True.

Empty List

Input: []
Output: True (vacuously true).

Complexity Breakdown

Two-Pointer with Reversal:

Time: O(n).
Space: O(1).

Stack-Based:

Time: O(n).
Space: O(n).

Reversal wins on space.

Key Takeaways for Beginners

Palindrome: Symmetry in sequence.
Two-Pointer: Finds middle, reverses half.
Stack: Mirrors list for comparison.
Python Tip: Linked list traversal—see [Python Basics](/python/basics).

Final Thoughts: Check Palindromes Like a Pro

LeetCode 234: Palindrome Linked List in Python is a fantastic linked list challenge. The two-pointer with reversal solution shines with its space-saving brilliance, while the stack-based approach keeps it simple. Want more linked list fun? Try LeetCode 206: Reverse Linked List or LeetCode 21: Merge Two Sorted Lists. Ready to test? Head to Solve LeetCode 234 on LeetCode and check that palindrome today!