Palindrome Linked List

Intuition

A linked list can only be traversed forward, but recursion lets us reach the tail and then process nodes in reverse as the call stack unwinds. We keep a front pointer, stored in an enclosing scope, that starts at the head. Each recursive call first dives all the way to the end of the list. As every frame returns, its node represents the list read from back to front, so we compare it with front, which is simultaneously walking from front to back. When the two ever disagree we propagate false; otherwise we advance front and keep unwinding. If all comparisons succeed the list is a palindrome.

Algorithm walkthrough

1. 1Initialize a front pointer to the head; it lives outside the recursive helper so every frame shares it.
2. 2In the helper, if the current node is null we have passed the tail, so return true as the base case.
3. 3Recurse on node.next first; if that returns false, short-circuit and return false immediately without further work.
4. 4Compare node.val (a value seen from the back) with front.val (a value seen from the front); if they differ return false.
5. 5Advance front to front.next and return true so the parent frame can compare the next outer pair.

Implementation

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        self.front = head

        def recurse(node: Optional[ListNode]) -> bool:
            if node is None:
                return True
            if not recurse(node.next):
                return False
            if node.val != self.front.val:
                return False
            self.front = self.front.next
            return True

        return recurse(head)