# 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:

```text
[1, 2, 2, 1]
```

is a palindrome.

But:

```text
[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

| Item | Meaning |
|---|---|
| Input | `head`, the first node of a singly linked list |
| Output | `True` if the list is a palindrome, otherwise `False` |
| Node values | Digits from `0` to `9` |
| Follow-up target | `O(n)` time and `O(1)` extra space |

LeetCode uses this node shape:

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

Function shape:

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

## Examples

Example 1:

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

The list reads:

```text
1 -> 2 -> 2 -> 1
```

From left to right, the values are:

```text
1, 2, 2, 1
```

From right to left, the values are also:

```text
1, 2, 2, 1
```

So the answer is `True`.

Example 2:

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

The list reads:

```text
1 -> 2
```

Forward order is:

```text
1, 2
```

Backward order is:

```text
2, 1
```

They differ, so the answer is `False`.

Example 3:

```text
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:

```text
1, 2
```

matches the reversed second half:

```text
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.

```python
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:

```text
1 -> 2 -> 2 -> 1
```

After reversing the second half:

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

Now we compare node by node.

## Finding the Middle

Use two pointers:

| Pointer | Movement |
|---|---|
| `slow` | Moves one step |
| `fast` | Moves two steps |

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

We use this setup:

```python
slow = head
fast = head
```

Then:

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

For odd length:

```text
1 -> 2 -> 3 -> 2 -> 1
```

`slow` stops at `3`.

For even length:

```text
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:

| Variable | Meaning |
|---|---|
| `prev` | Previous node in the reversed list |
| `cur` | Current node being processed |
| `nxt` | Saved next node before changing links |

Starting from `slow`, reverse the rest of the list:

```python
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:

```text
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We find the middle, reverse half, then compare half |
| Space | `O(1)` | Only pointer variables are used |

Here, `n` is the number of nodes.

## Implementation

```python
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:

```python
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:

```python
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:

```python
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.

```python
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:

```python
return True
```

## Testing

```python
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
```

```python
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()
```

| Test | Why |
|---|---|
| `[1,2,2,1]` | Even-length palindrome |
| `[1,2]` | Small non-palindrome |
| `[1]` | Single node |
| `[1,2,3,2,1]` | Odd-length palindrome |
| `[1,2,3,4,1]` | Same ends but different middle |
| `[0,0]` | Duplicate zero values |