Edit Problem

Title

Problem URL

Difficulty

Tags

Fast & Slow Pointers

Go file path (optional)

Notes (optional)

## What It Does

This function checks whether a linked list reads the same forwards and backwards. It does this in three distinct phases without any extra storage:

1. **Find the middle** — tortoise-and-hare gets `slow` to the midpoint (second middle for even-length lists, as we covered).
2. **Reverse the second half in-place** — starting from `slow`, the standard pointer reversal (`next → current → prev`) walks to the end, flipping every `Next` pointer. After this, `current` (which ends as the old tail) is the new head of the reversed second half.
3. **Compare both halves** — `left` starts at `head`, `right` starts at the reversed tail, and they walk inward together. Any value mismatch means it's not a palindrome.

For example, `1 → 2 → 3 → 2 → 1`: the second half reverses to `1 → 2 → 3`, and comparing left-to-right against the original gives `1==1`, `2==2`, `3==3` — returns `true`. For `1 → 2 → 3`: mismatch at `1 vs 3` — returns `false`.

---

## Complexity Analysis

**Time Complexity: O(n)**
Three separate linear passes — find middle, reverse, compare — each O(n). Constants collapse, still O(n) overall.

**Space Complexity: O(1)**
Pure in-place pointer manipulation. No auxiliary list, no stack, no recursion. Just a handful of pointer variables.

---

## A Few Notes

**The reversal loop uses `break` instead of the standard `for current != nil` guard.** This is intentional — a normal `for current != nil` would exit before processing the last node, leaving `prev` pointing to the second-to-last. Using `break` after the nil check on `next` ensures the final node gets reversed and `current` ends up as the true new head of the reversed half. Subtle but important.

**The list is left mutated after this call.** The second half remains reversed when the function returns. For a coding challenge that's fine, but in production you'd want a third pass to restore the original structure before returning — especially if other code holds references to nodes in the list.

**This is the direct payoff of the two previous problems.** You literally composed `middle_of_the_linkedlist` and a standard reversal — the palindrome check is just the glue. Recognizing these as composable primitives is exactly the right way to think about the fast/slow pointer pattern family.

First solved

May 28, 2026