Reverse Linked List

Problem

You are given the head of a singly linked list. Reverse the order of the nodes in place so that the last node becomes the first, and return the new head. You may not allocate new list nodes; only pointer fields may change.

• The list contains between 0 and 8,000 nodes.
• Node values fit in a signed 32-bit integer.

Examples

• 4 -> 8 -> 15 -> 16 -> 23 -> 42 → 42 -> 23 -> 16 -> 15 -> 8 -> 4.
• -3 -> 9 → 9 -> -3. Two nodes: the old tail becomes the head.
• empty list → empty list. A single node is likewise returned unchanged.

Hints

1. To make a node point backwards you need to know its predecessor, which a singly linked node does not store.
2. Walk the list keeping the previous node in a variable. Before you redirect node.next, save the old next or you lose the rest of the list.
3. Three pointers (prev, curr, nxt): redirect, then advance all three. The recursive version reverses the tail first and then hooks the head onto its end.