234. Palindrome Linked List

Reformulated question¶

Given the head of a singly linked list, return whether its values read the same forward and backward.

Example:

[1, 2, 2, 1] -> True
[1, 2] -> False

Key trick¶

Use slow/fast pointers to find the middle, reverse the second half in place, then compare both halves.

Trap¶

Forgetting odd length handling:
- skip the middle node before comparing.
Using extra array memory:
- works, but misses the \(O(1)\) extra space follow-up.
Mutating nodes by adding prev on a singly linked list:
- this changes the data structure instead of solving the problem.
Crashing on small lists:
- especially when accessing right.next without checking right.

Why this question is interesting¶

It combines three classic linked-list skills in one problem:

find middle
reverse list
compare halves

It is a clean test of pointer manipulation and edge-case control.

Solve the problem with idiomatic Python¶

from typing import Optional
from utils import ListNode

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # 0 or 1 node is always a palindrome.
        if head is None or head.next is None:
            return True

        # Find the middle.
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # For odd length, skip the middle node.
        if fast:
            slow = slow.next

        # Reverse the second half in place.
        prev = None
        curr = slow
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt

        # Compare first half with reversed second half.
        left = head
        right = prev
        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next

        return True

Pytest test¶

import pytest
from utils import list_build

@pytest.mark.parametrize(
    ("values", "expected"),
    [
        ([1], True),
        ([1, 1], True),
        ([1, 2], False),
        ([1, 2, 1], True),
        ([1, 2, 2, 1], True),
        ([1, 2, 3, 2, 1], True),
        ([1, 2, 3, 4, 1], False),
        ([1, 0, 1], True),
        ([1, 2, 3, 2, 2], False),
    ],
)
def test_is_palindrome(values, expected):
    head = list_build(values)
    assert Solution().isPalindrome(head) is expected

Comment my solution¶

Good:
- compares symmetric values from both ends.
Problems:
- it adds a prev attribute to nodes, which is not part of a singly linked list.
- it needs a full pass to count and another to compare from the end, instead of using the standard reverse-half approach.
- it can fail conceptually in interview settings because modifying the node shape is usually considered invalid.
- while right.next: assumes right exists and is less robust than the standard slow/fast solution.
Interview-wise:
- prefer reverse-second-half in place, because it matches the intended \(O(n)\) time and \(O(1)\) extra space solution cleanly.

from typing import Optional
import pytest
from utils import ListNode, list_build

class Solution:
    def isPalindrome(self, head: Optional[ListNode],) -> bool:
        left = head
        right = head
        count = 1
        while right.next:
            prev = right
            right = right.next
            right.prev = prev
            count += 1

        for i in range(count // 2):
            if left.val != right.val:
                return False
            left = left.next
            right = right.prev
        return True

@pytest.mark.parametrize(
    ("values", "is_palindrome"),
    [
        ([1,2,2,1], True),
        ([1,2], False)
    ],
)
def test_isPalindrome(values, is_palindrome):
    head = list_build(values)
    assert Solution().isPalindrome(head) == is_palindrome