In-Place Pointer Reversal

Foundations

An array keeps its elements in contiguous slots, so nums[i] is one address calculation away. A linked list gives up that layout: each value lives in a separate node object anywhere in memory, and each node stores a .next reference to the node after it, with None after the last. The list is reached through its first node, head, so reaching the ith node means following i links: O(i), not O(1).

The trade is that rearranging is cheap: changing one .next reference moves a whole chain without shifting any element. Reversing a list in place walks it once with three references: prev, the head of the part already reversed; curr, the node being rewired; and nxt, saved before curr.next changes, because that link is the only way to reach the rest.

Build nums = [7, 1, 5, 3, 6] as 7 → 1 → 5 → 3 → 6 → None. Midway through a reversal, 7 and 1 already point backward: 1 → 7 → None is the reversed part, prev is 1, and curr is 5. Save nxt = 3, point 5's .next at 1, then step: prev = 5 and curr = 3. Each node is rewired once, and no node is copied.

• Arrays & Strings

  Linked lists make the opposite trade from arrays. That lesson shows why array indexing is O(1).

  Open lesson

Case Scenario

Reverse Linked List gives head and asks for the same nodes in reverse order, returning the new head. For head = [1, 2, 3, 4], that is 4 → 3 → 2 → 1: one pass flips each .next to point backward, and the old tail, 4, becomes the head. No values move and no nodes are created; only links change.

The direct approach copies every value into an array, then walks the list again writing them back in reverse. The order comes out right, but the copy costs O(n) extra memory, and it moves values instead of links, so code that holds a reference to a node suddenly finds a different value inside it.