How Linked List works

Before you start

• Arrays & Strings

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

  Open lesson

Why it matters

Queues, cache eviction lists, and memory allocators often need to change traversal order without copying their records. Rebuilding a list raises peak memory and can break code that holds references to existing nodes. For 1 → 2 → 3 → 4, return 4 → 3 → 2 → 1 with O(1) extra space while reusing every node and preserving access to the unread suffix.

Reverse the singly linked list and return the new head. Tests pass and expect arrays of node values.

Input

head = [1, 2, 3, 4]

Output

[4, 3, 2, 1]

On 1 → 2 → 3 → 4, save node 2 before changing 1.next to None, then repeat until 4 points to 3. Flipping links in place avoids the brute copy of all four values and a second write-back pass.

Start with prev = None and curr at node 1. Save nxt = 2 before changing 1.next to None; otherwise nodes 2, 3, and 4 become unreachable. Then move prev to 1 and curr to the saved node 2.

At node 2, save 3 and point 2.next back to 1. Repeat for 3 and 4. prev always heads the reversed prefix, curr is the node being changed, and nxt preserves the untouched suffix. When curr becomes None, prev is node 4, the new head.