Reverse linked list

Given the head of a singly linked list, reverse the list and return the new head.

Before you code

Don't create new nodes or copy values. Every node stays where it is; only its next pointer changes. Write down the loop invariant before the loop: what do prev and curr each head?

Hints

1. Keep three pointers: prev (reversed so far), curr (next to process) and nxt (saved before overwriting).
2. Each pass: save curr.next, point curr.next at prev, then advance prev and curr.
3. Return prev, not head. The old head is now the tail.
4. Then write the recursive version and compare its stack usage on a list of 100,000 nodes.

Production & complexity notes

When solving Reverse linked list on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Nodes and pointers to reinforce the underlying pattern.

What it practices

Rewiring pointers in a safe order, from Nodes and pointers.