Palindrome Linked List | Leetcode 234 | Optimal Solution

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

Here’s the [Problem Link] to begin with.

Example 1:

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

Example 2:

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

Constraints:

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

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

Solution 1: Brute Force Approach (Using Stack)

Intuition

Think of this like reading a book and checking if it’s the same when you read it backward! One simple way is to write down all the words on pieces of paper, stack them up, then pick them from the top (which gives you the reverse order) and compare with the original book. If they match perfectly, it’s a palindrome!

Detailed Approach

1. First Pass: Walk through the entire linked list and store all node values in a stack
2. Second Pass: Walk through the linked list again and compare each node’s value with values popped from the stack
3. Stack Magic: Since stack follows LIFO (Last In, First Out), popping gives us values in reverse order
4. Comparison: If all values match during comparison, it’s a palindrome
5. Early Exit: If any value doesn’t match, return false immediately

Code

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        temp = head
        stack = []
        
        # First pass: Store all values in stack
        while temp is not None:
            stack.append(temp.val)  # Push current node's value to stack
            temp = temp.next
        
        temp = head  # Reset temp to head for second pass
        
        # Second pass: Compare with stack values (reverse order)
        while temp is not None:
            if temp.val != stack.pop():  # Compare with stack's top value
                return False             # Not a palindrome
            temp = temp.next
        
        return True  # All values matched - it's a palindrome!

Code Explanation

We use two separate loops here. In the first loop, we visit every node and push its value onto our stack. This stores all values with the last value at the top. In the second loop, we visit each node again and compare its value with the value we pop from the stack. Since stack gives us values in reverse order, we’re essentially comparing the original list with its reverse. If all values match, we have a palindrome.

Dry Run

Let’s trace through: 1 -> 2 -> 2 -> 1

First Pass:

• Visit node 1: stack = 
• Visit node 2: stack = 
• Visit node 2: stack = 
• Visit node 1: stack = 

Second Pass:

• Visit node 1: pop 1 from stack, 1 == 1 ✓
• Visit node 2: pop 2 from stack, 2 == 2 ✓
• Visit node 2: pop 2 from stack, 2 == 2 ✓
• Visit node 1: pop 1 from stack, 1 == 1 ✓

Result: All values matched, return True!

Time and Space Complexity

• Time Complexity: O(n) – We traverse the list twice
• Space Complexity: O(n) – We store all values in the stack

Simplifying It

This approach is straightforward – store everything, then compare with the reverse. It’s like taking a photo of text and comparing it with the same photo flipped horizontally. Easy to understand but uses extra memory for storage.

Solution 2: Optimal Approach (Two Pointers + Reverse)

Intuition

Imagine you have a book and want to check if it’s a palindrome without making copies. Here’s a clever trick: find the middle of the book, then flip all pages after the middle backward. Now compare the first half with the flipped second half page by page. If they match perfectly, your book is a palindrome!

Detailed Approach

1. Find the Middle: Use two pointers (slow and fast) to find the middle of the linked list
2. Reverse Second Half: Reverse the second half of the linked list
3. Compare Both Halves: Compare the first half with the reversed second half
4. Check for Mismatch: If any values don’t match, it’s not a palindrome
5. Restore Original: Optionally reverse the second half back to restore the original list

Code

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        temp = head
        while temp is not None:
            front = temp.next    # Store next node
            temp.next = prev     # Reverse the link
            prev = temp          # Move prev forward
            temp = front         # Move temp forward
        return prev             # Return new head of reversed list

    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if head is None or head.next is None:
            return True         # Empty list or single node is palindrome
        
        slow = head
        fast = head
        
        # Find the middle of the linked list
        while fast.next and fast.next.next:
            slow = slow.next        # Move slow 1 step
            fast = fast.next.next   # Move fast 2 steps
        
        # Reverse the second half
        new_head = self.reverseList(slow.next)
        
        # Compare first half with reversed second half
        first = head
        second = new_head
        while second is not None:
            if first.val != second.val:
                return False    # Values don't match
            first = first.next
            second = second.next
        
        # Restore original list structure (optional)
        self.reverseList(new_head)
        return True

Code Explanation

This solution works in multiple steps. First, we find the middle of the list using the two-pointer technique where slow moves 1 step and fast moves 2 steps. When fast reaches the end, slow is at the middle. Then we reverse the second half of the list starting from the node after the middle. Finally, we compare the first half with the reversed second half. If all values match, we have a palindrome. We also restore the original list structure at the end.

Dry Run

Let’s trace through: 1 -> 2 -> 2 -> 1

Step 1 – Find Middle:

• Initial: slow=1, fast=1
• Step 1: slow=2, fast=2 (second occurrence)
• Step 2: slow=2, fast=None (fast.next.next doesn’t exist)
• Middle found: slow points to second 2

Step 2 – Reverse Second Half:

• Second half starts after slow: 1 -> None
• After reversal: 1 -> None (single node, no change)

Step 3 – Compare:

• First half: 1 -> 2
• Second half: 1
• Compare: 1==1 ✓, 2==? (second half exhausted)
• All matched!

Result: Return True!

Time and Space Complexity

• Time Complexity: O(n) – We traverse the list a few times but still linear
• Space Complexity: O(1) – We only use a few pointer variables

Simplifying It

This approach is like folding a paper in half and checking if both sides match perfectly. We find the middle, flip one half, and compare. It’s more complex to understand but much more memory-efficient since we don’t need extra storage space.

Key Insights

Why does the middle-finding work?
When fast moves 2 steps and slow moves 1 step, fast covers twice the distance. When fast reaches the end, slow is exactly at the middle. It’s like two people walking where one walks twice as fast – when the faster person reaches the destination, the slower person is halfway there.

Why reverse only the second half?
Reversing the second half allows us to compare both halves by moving forward in both. It’s like flipping one half of a mirror image to see if both sides are identical.

Summary

The two pointers approach is generally preferred because it uses constant space while maintaining the same time efficiency. However, the brute force approach is more intuitive and easier to understand when you’re first learning about palindrome detection.

Both solutions effectively solve the problem, but the optimal solution showcases advanced linked list manipulation techniques that are valuable for solving many other problems!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.