109 Find if Its Palindrome Linked List

 

Approach: Fast & Slow Pointer + Reverse Second Half

This is the most optimal solution with:

• Time Complexity: O(n)

• Space Complexity: O(1) (no extra space used)

Steps:

1. Use fast and slow pointers to find the middle.

2. Reverse the second half of the list.

3. Compare both halves node by node.

4. (Optional) Restore the list by reversing the second half again.

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

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head or not head.next:
            return True
        
        # Step 1: Find the middle using fast and slow pointers
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # Step 2: Reverse the second half
        prev = None
        curr = slow
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
        
        # Step 3: Compare first half and reversed second half
        first, second = head, prev
        while second:
            if first.val != second.val:
                return False
            first = first.next
            second = second.next
        
        return True