LeetCode 206 Reverse Linked List - Example and Complexity Analysis

Trace 1 → 2 → 3 → null.

Initialize: prev = null, curr = 1.

Step 1: next = 2. Point 1.next = null. Move: prev = 1, curr = 2. State: null ← 1 2 → 3 → null

Step 2: next = 3. Point 2.next = 1. Move: prev = 2, curr = 3. State: null ← 1 ← 2 3 → null

Step 3: next = null. Point 3.next = 2. Move: prev = 3, curr = null. State: null ← 1 ← 2 ← 3

curr is null. Return prev = 3. New list: 3 → 2 → 1 → null.

Each node visited once. $O(n)$ time. Only three pointers used. $O(1)$ space.