Palindrome Linked List

Roman to Integer

Longest Palindromic Substring

Check whether the values represented by a singly linked list form a palindrome.

Determine whether the values in a singly linked list read the same forward and backward. In the current judge contract, `head` is serialized as an integer array in traversal order.

**Input / output**
- Input: `head: integer[]` representing linked-list node values
- Output: boolean

**Examples**
1. `[1,2,2,1]` returns `true`.
2. `[1,2]` returns `false`.

**Constraints**
- `1 <= head.length <= 100,000`
- `-100,000 <= head[i] <= 100,000`

**Follow-up**
With real nodes, can you solve it in linear time and constant space while restoring the list afterward?

- A linked list is a palindrome when its node values read the same forwards and backwards.
- The interview challenge is doing this in `O(1)` extra space — you cannot index into a linked list, and copying all values to an array uses `O(n)` space.
- The trick is to reverse only the second half in place and compare it against the first half.

Understand the Goal

- Advance a `slow` pointer one node at a time and a `fast` pointer two nodes at a time.
- When `fast` reaches the end, `slow` sits at the middle of the list.
- With the array framing, the same idea is a midpoint index `len(head) // 2`.

Find the Middle with Fast/Slow Pointers

- Reverse the second half of the list (in the real linked-list version this is an in-place pointer reversal).
- Walk both halves in step and compare values; if any pair differs, it is not a palindrome.
- An odd-length middle element can be ignored because it mirrors itself.

Reverse the Second Half and Compare

- Finding the middle, reversing the second half, and comparing each take a single pass, so the total time is `O(n)`.
- The in-place reversal keeps extra space at `O(1)` for a true linked list. With the array framing, a symmetric two-pointer scan is the simplest correct approach.