EasyLinked ListTwo PointersRecursionStack

Palindrome Linked List

1 approach, code in every language

Given the head of a singly linked list, determine whether the sequence of values forms a palindrome, meaning it is identical when read from front to back and from back to front.

Return true when the values are symmetric and false otherwise. An empty list and a single-node list are trivially palindromes.

Example 1

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

Output: true

Reading the values forward gives 1,2,2,1 and reading them backward gives the same sequence.

Example 2

Input: head = [1,2,3]

Output: false

Forward the values are 1,2,3 but backward they are 3,2,1, so the list is not symmetric.

Constraints

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

Recursion

Recurse to the tail, then compare nodes from the back against a front pointer that advances as the recursion unwinds.

Loading animation…

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

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

Time

O(n)

Space

O(n)

The recursion descends to the tail, using O(n) stack frames, and each frame does O(1) work.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Linked List

After the pattern

Now solve one you haven't seen.

Stamp Chain Echo is our own problem on the technique behind Palindrome Linked List: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free