Palindrome Linked List | Leetcode 234

Welcome to our multi-approach showcase on Palindrome Linked List (Leetcode 234). A standard Palindrome validation takes fractions of a second when analyzing native Strings or Arrays using left/right index pointers. But a Linked List has no backward .prev pointer, making this a spectacular test of pointer manipulation.

Problem Statement

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

Example 1: head = [1, 2, 2, 1] => Output: true

Example 2: head = [1, 2] => Output: false

Approach 1: Array Conversion O(N) Time | O(N) Space

The absolute simplest brute-force approach ignores the Linked List properties entirely. We traverse the entire Linked List from start to end, taking the value of every node we see and pushing it into a dynamic Array (or List).

Once the array is constructed, we natively use two standard integer pointers (left and right) to verify the symmetry of the array just like a standard string!

# 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: Optional[ListNode]) -> bool:
        vals = []
        curr = head
        
        # Sequentially drain list values into Python list
        while curr:
            vals.append(curr.val)
            curr = curr.next
            
        # Two-pointer validation
        left, right = 0, len(vals) - 1
        
        while left < right:
            if vals[left] != vals[right]:
                return False
            left += 1
            right -= 1
            
        return True

Complexity Analysis

Approach 2: Reverse Second Half In-Place O(N) Time | O(1) Space

Can you achieve O(1) memory by analyzing the list natively without allocating an array wrapper? Yes, absolutely. We combine two legendary algorithm primitives: Fast/Slow Cycle Pointers and Linked List Reversal.

1. Using a fast and slow pointer traversing at 2x and 1x speed natively, drive fast completely off the edge of the queue. By doing this, the slow pointer perfectly lands physically on the middle node.
2. We detach that second half and run a classic pointer reversal loop purely on it. By the end, the tail conceptually points "backwards" to the middle!
3. Compare the original head string sequentially jumping toward the middle, against the newly inverted tail string jumping backward to the middle!

graph LR
    A["Middle Discovered"]
    B["Original List: 1 --> 2 --> 2 --> 1"]
    
    A -->|1. Find Center| C["1 --> 2 (slow) --> 2 --> 1"]
    C -->|2. Sever & Invert Tail| D["1 --> 2<br> 1 --> 2 (inverted tail)"]
    D -->|3. Dual Synchronized Pointers Verify Match!| E(("TRUE"))

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next: return True
        
        # 1. Drive Fast/Slow to locate absolute center
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
        # 2. Reverse the extracted right-half
        prev = None
        curr = slow
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
            
        # 3. Synchronize validation loop starting from outside bounds
        left = head
        right = prev  # The reversed tail acts as the start of the right side!
        
        while right: 
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
            
        return True

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (234)