LeetCode 234: Palindrome Linked List

Problem Restatement

We are given the head of a singly linked list.

We need to return True if the linked list is a palindrome, and False otherwise.

A palindrome reads the same forward and backward.

For example:

[1, 2, 2, 1]

is a palindrome.

But:

[1, 2]

is not a palindrome.

LeetCode examples include head = [1,2,2,1], which returns true, and head = [1,2], which returns false. The list length is between 1 and 10^5, and each node value is between 0 and 9. The follow-up asks for O(n) time and O(1) space.

Input and Output

LeetCode uses this node shape:

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

Function shape:

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

Examples

Example 1:

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

The list reads:

1 -> 2 -> 2 -> 1

From left to right, the values are:

1, 2, 2, 1

From right to left, the values are also:

1, 2, 2, 1

So the answer is True.

Example 2:

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

The list reads:

1 -> 2

Forward order is:

1, 2

Backward order is:

2, 1

They differ, so the answer is False.

Example 3:

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

The middle value 3 does not need to be compared with another node.

The first half:

1, 2

matches the reversed second half:

1, 2

First Thought: Copy Values Into an Array

The simplest approach is to copy all linked list values into an array.

Then we can check whether the array equals its reverse.

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

        cur = head
        while cur is not None:
            values.append(cur.val)
            cur = cur.next

        return values == values[::-1]

This is easy and correct.

But it uses O(n) extra space for the array.

The follow-up asks for O(1) extra space, so we need a method that works directly on the linked list.

Key Insight

A singly linked list cannot move backward.

So to compare the first half with the second half, we need to make the second half readable in reverse order.

We can do this by reversing the second half of the linked list in place.

The full plan is:

1. Find the middle of the list.
2. Reverse the second half.
3. Compare the first half with the reversed second half.

For example:

1 -> 2 -> 2 -> 1

After reversing the second half:

first half:           1 -> 2
reversed second half: 1 -> 2

Now we compare node by node.

Finding the Middle

Use two pointers:

When fast reaches the end, slow is near the middle.

We use this setup:

slow = head
fast = head

Then:

while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

For odd length:

1 -> 2 -> 3 -> 2 -> 1

slow stops at 3.

For even length:

1 -> 2 -> 2 -> 1

slow stops at the second 2.

In both cases, slow can be used as the start of the second half. For odd length, the middle node will be included in the reversed part, but this causes no problem because the comparison stops when the shorter side ends.

Reversing the Second Half

To reverse a linked list, use three pointers:

Starting from slow, reverse the rest of the list:

prev = None
cur = slow

while cur:
    nxt = cur.next
    cur.next = prev
    prev = cur
    cur = nxt

After this loop, prev points to the head of the reversed second half.

Algorithm

1. Use fast and slow pointers to find the middle.
2. Reverse the list starting from slow.
3. Compare:
   • left starts at head
   • right starts at the reversed second half
4. While right exists:
   • If values differ, return False
   • Move both pointers forward
5. Return True

We compare while right exists because the reversed second half is the part we must match.

Correctness

The fast and slow pointer loop places slow at the beginning of the second half for even-length lists, or at the middle node for odd-length lists.

Reversing from slow makes the right side readable from the original tail toward the middle.

For a palindrome, the first value must equal the last value, the second value must equal the second-to-last value, and so on.

After reversal, those values become aligned:

left pointer:   first, second, third, ...
right pointer:  last, second-last, third-last, ...

The algorithm compares exactly these corresponding values.

If any pair differs, the list cannot be a palindrome, so returning False is correct.

If all compared pairs match, then every value in the first half matches the corresponding value in the second half. For odd-length lists, the middle node may compare with itself or be safely passed through as part of the reversed side, and it does not affect palindrome validity.

Therefore, the algorithm returns True exactly when the linked list is a palindrome.

Complexity

Here, n is the number of nodes.

Implementation

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

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        prev = None
        cur = slow

        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt

        left = head
        right = prev

        while right:
            if left.val != right.val:
                return False

            left = left.next
            right = right.next

        return True

Code Explanation

First we find the middle:

slow = head
fast = head

while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

fast moves twice as quickly as slow. When fast reaches the end, slow is at the middle area.

Then we reverse the second half:

prev = None
cur = slow

while cur:
    nxt = cur.next
    cur.next = prev
    prev = cur
    cur = nxt

At the end of this loop, prev is the head of the reversed second half.

Then we compare:

left = head
right = prev

The left pointer walks from the original head.

The right pointer walks from the original tail backward, because the second half has been reversed.

while right:
    if left.val != right.val:
        return False

If a mismatch appears, the list is not a palindrome.

If the loop finishes, all required pairs match:

return True

Testing

from typing import Optional

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

def build_list(values):
    dummy = ListNode()
    cur = dummy

    for value in values:
        cur.next = ListNode(value)
        cur = cur.next

    return dummy.next

def run_tests():
    s = Solution()

    assert s.isPalindrome(build_list([1, 2, 2, 1])) is True
    assert s.isPalindrome(build_list([1, 2])) is False
    assert s.isPalindrome(build_list([1])) is True
    assert s.isPalindrome(build_list([1, 2, 3, 2, 1])) is True
    assert s.isPalindrome(build_list([1, 2, 3, 4, 1])) is False
    assert s.isPalindrome(build_list([0, 0])) is True

    print("all tests passed")

run_tests()