Edit Problem

Title

Problem URL

Difficulty

Tags

Fast & Slow Pointers

Go file path (optional)

Notes (optional)

## What It Does

This function reorders a linked list from `L0 → L1 → L2 → ... → Ln` into `L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...` — interleaving nodes from the front and back, in-place. It does this in three phases you've now seen individually:

1. **Find the middle** — tortoise-and-hare lands `slow` at the midpoint, splitting the list in two.
2. **Reverse the second half** — `slow.Next = nil` cleanly severs the two halves before reversing. Unlike the palindrome solution, `previous` is initialized to `slow` (the mid node) rather than `nil`, so the mid node becomes the tail of the reversed half rather than being detached.
3. **Interleave (stitch)** — `first_half` and `second_half` walk inward together, weaving one node from each side per iteration. The `if first_half_next != nil` guard prevents the last second-half node from clobbering an already-correct `Next` pointer near the end.

For example, `1 → 2 → 3 → 4 → 5` becomes `1 → 5 → 2 → 4 → 3`. The mid node `3` ends up as the tail naturally since `second_half` runs out after it.

---

## Complexity Analysis

**Time Complexity: O(n)**
Three linear passes — find middle, reverse, interleave — each O(n), collapsing to O(n) overall.

**Space Complexity: O(1)**
Entirely in-place pointer rewiring. No new nodes, no auxiliary storage beyond a few local variables.

---

## A Few Notes

**The reversal here differs subtly from the palindrome version.** There, `prev` started as `nil` making the mid node's `Next` point to `nil` (clean tail). Here, `previous` starts as `slow` and `slow.Next` is severed beforehand — so the mid node folds into the reversed half as its own tail. Worth being deliberate about which variant you reach for depending on whether you want the mid node included or excluded from the reversal.

**The `if first_half_next != nil` guard is load-bearing.** Without it, on the last iteration `second_half.Next` would get overwritten to `nil` (or a stale pointer), potentially cutting off the remaining tail. It's easy to miss in the happy path but breaks even-length lists without it.

**This is the full composition of everything prior.** Middle-finding, in-place reversal, and two-pointer traversal — all three primitives from the last few problems assembled into one. If the pattern wasn't obvious before, it should be now: fast/slow isn't just a trick, it's a reusable toolkit.

First solved

May 28, 2026