234. Palindrome Linked List - Explanation

Description

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

A palindrome is a sequence that reads the same forward and backward.

Example 1:

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

Output: true

Example 2:

Input: head = [2,2]

Output: true

Example 3:

Input: head = [2,1]

Output: false

Constraints:

1 <= Length of the list <= 100,000.
0 <= Node.val <= 9

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

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Convert To Array

Intuition

A palindrome reads the same forwards and backwards. Linked lists only allow forward traversal, making direct comparison difficult. The simplest approach is to convert the linked list to an array where we can use random access.

Once we have an array, we can use two pointers from both ends moving toward the center, comparing values as we go.

Algorithm

Traverse the linked list and store all node values in an array.
Initialize two pointers: left at the start and right at the end of the array.
While left < right, compare arr[left] and arr[right]. If they differ, return false.
Move left forward and right backward after each comparison.
If all comparisons pass, return true.

# 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:
        arr = []
        cur = head
        while cur:
            arr.append(cur.val)
            cur = cur.next

        l, r = 0, len(arr) - 1
        while l < r:
            if arr[l] != arr[r]:
                return False
            l, r = l + 1, r - 1

        return True

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Recursion

Intuition

We can use recursion to simulate traversing from the end of the list. By recursing to the end first and comparing on the way back, we effectively compare nodes from both ends simultaneously.

We maintain a pointer starting at the head. As recursion unwinds from the tail, we compare each node with the head pointer and advance the head pointer after each match.

Algorithm

Initialize a pointer cur at the head of the list.
Define a recursive function rec(node) that:
- Returns true if node is null (base case).
- Recursively calls rec(node.next) first to reach the end.
- Compares cur.val with node.val. If they differ, return false.
- Advances cur to the next node.
- Returns true if all comparisons pass.
Call rec(head) and return the result.

# 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:
        self.cur = head

        def rec(node):
            if node is not None:
                if not rec(node.next):
                    return False
                if self.cur.val != node.val:
                    return False
                self.cur = self.cur.next
            return True

        return rec(head)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for recursion stack.

3. Stack

Intuition

A stack provides LIFO (last-in-first-out) access. If we push all elements onto a stack and then traverse the list while popping, we compare elements from the front and back simultaneously.

This is similar to the array approach but uses a stack to reverse the order of comparison.

Algorithm

Traverse the linked list and push all values onto a stack.
Traverse the list again from the head. For each node, pop from the stack and compare.
If any comparison fails, return false.
If we complete the traversal without mismatches, return true.

# 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:
        stack = []
        cur = head

        while cur:
            stack.append(cur.val)
            cur = cur.next

        cur = head
        while cur and cur.val == stack.pop():
            cur = cur.next

        return not cur

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Fast & Slow Pointers

Intuition

To achieve O(1) extra space, we can reverse the second half of the list in place. Then we compare the first half with the reversed second half node by node.

We use the fast and slow pointer technique to find the middle of the list. The fast pointer moves twice as fast, so when it reaches the end, the slow pointer is at the middle.

Algorithm

Use fast and slow pointers to find the middle of the list. When fast reaches the end, slow is at the middle.
Reverse the second half of the list starting from slow.
Compare nodes from the head and from the reversed second half. If any values differ, return false.
Continue until the reversed half is fully traversed.
Return true if all comparisons match.

# 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: ListNode) -> bool:
        fast = head
        slow = head

        # find middle (slow)
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        # reverse second half
        prev = None
        while slow:
            tmp = slow.next
            slow.next = prev
            prev = slow
            slow = tmp

        # check palindrome
        left, right = head, prev
        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next

        return True

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

Common Pitfalls

Incorrect Middle Finding for Odd-Length Lists

When using fast and slow pointers, for odd-length lists the slow pointer ends up at the exact middle element. If you reverse starting from slow, the middle element ends up in the reversed half. This still works because we only compare until the reversed half is exhausted, but misunderstanding this can lead to off-by-one errors in the comparison loop.

Not Restoring the Original List

The in-place reversal approach modifies the original linked list structure. If the problem requires the list to remain unchanged after the function call, or if subsequent operations depend on the original structure, you must reverse the second half back to its original order after the palindrome check.