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

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!