Reverse Linked List

Learning goal: Understand what must change when reversing a singly linked list.

Core idea A linked list is determined by its next pointers, not by the physical order of its nodes. Reversal means every node should point to the node that appeared immediately before it. The old head becomes the tail, so its next must become null; the old tail becomes the new head.

Algorithm plan

• Start with prev = null and current = head.
• While current is not null, process one link.
• Save the node after current in temp.
• Point current.next backward to prev.
• Advance both pointers: prev = current, then current = temp.
• Return prev after the walk ends.

Micro-example For 1 -> 2 -> 3 -> 4, the first reversal changes 1 -> 2 into 1 -> null. The remaining unprocessed list still begins at 2, because it was saved in temp.

Pitfalls

• The answer is the final prev, not the original head.
• An empty list should return null.
• A one-node list is already reversed.

Recap

• Reverse links, not node values.
• The old tail becomes the new head.
• Preserve access to the unreversed suffix before changing a pointer.

Learning goal: Use prev and current to describe the reversed and unreversed parts of the list.

Core idea At every moment, the list is split into two regions. The nodes from the new head through prev are already reversed, while current begins the untouched suffix. The key operation joins the next node from the untouched suffix to the front of the reversed region.

Data structure model

while current != null:
    temp = current.next
    current.next = prev
    prev = current
    current = temp

Micro-example Before processing 3, the reversed prefix is 2 -> 1 -> null and the suffix is 3 -> 4. Redirecting 3.next to 2 produces 3 -> 2 -> 1, while temp preserves access to 4.

Pitfalls

• Do not move current before saving its successor.
• Do not confuse the reversed prefix with the original prefix.
• The invariant must hold after every loop iteration.

Recap

• prev is the head of the reversed region.
• current is the head of the remaining region.
• One saved pointer makes the in-place update safe.

Learning goal: Translate the invariant into a complete iterative algorithm.

Core idea The algorithm processes each node exactly once. Before changing a link, it records where the unreversed suffix continues; then it flips one arrow and advances the boundary between the two regions. Because no new nodes or auxiliary list are needed, the reversal happens in place.

Algorithm plan

1. Initialize prev to null and current to head.
2. Store current.next in temp.
3. Set current.next = prev to reverse one link.
4. Move prev to current.
5. Move current to temp.
6. Return prev when current reaches null.

def reverseList(head):
    prev, current = None, head
    while current:
        temp = current.next
        current.next = prev
        prev = current
        current = temp
    return prev

Micro-example For [1,2,3,4], the boundary moves as follows: null | 1 2 3 4, then 1 | 2 3 4, then 2 1 | 3 4, and finally 4 3 2 1 |.

Pitfalls

• The assignment current.next = prev must occur after temp = current.next.
• Returning head returns the old first node, now the tail.
• Avoid allocating an array or a second set of nodes; neither is necessary.

Recap

• Each iteration saves, flips, and advances.
• The loop ends exactly when the original suffix is exhausted.
• The final prev is the reversed list's head.

Learning goal: Trace every pointer update on the example [1,2,3,4].

Core idea Each iteration performs one local reversal while preserving the rest of the chain. The visualization separates the saved successor from the pointer that is being rewritten, making the critical update order explicit.

Pointer movement

Micro-example At the final iteration, current is 4 and temp is null. Setting 4.next = 3 completes the reversal; advancing makes current = null and leaves prev = 4.

Pitfalls

• The old edge 3 -> 4 must be remembered before changing 4.next.
• A null temp is normal on the final iteration.
• Follow next from the returned node to verify the final order.

Recap

• Four nodes require four pointer flips.
• The final chain is 4 -> 3 -> 2 -> 1 -> null.
• prev is the only pointer needed after the loop.

Learning goal: Recognize the pointer-ordering mistake that can destroy access to the remaining list.

Core idea The dangerous line is current.next = prev. It is necessary, but it overwrites the only link from current to the unreversed suffix. Therefore, temp = current.next must happen first. This is the central safety rule for in-place linked-list mutation.

Edge cases

• Empty list: head = null; the loop does not run and the result is null.
• One node: Its link is already null; return that node unchanged.
• Two nodes: One flip changes a -> b into b -> a.
• Long list: The same constant-space loop works without recursion depth concerns.

Micro-example For 1 -> 2 -> 3, the incorrect order sets 1.next = null and then tries to advance using 1.next; node 2 is no longer reachable. The correct order stores node 2 in temp before setting 1.next = null.

Pitfalls

• Do not use the changed current.next as the next node.
• Do not return the old head.
• Do not create a cycle by pointing the final node anywhere except its processed predecessor.

Recap

• Save, flip, advance is the safe order.
• null inputs are handled naturally.
• Each link must be changed once, with no accidental cycle.

Learning goal: Justify why iterative reversal meets the target efficiency.

Core idea The loop visits each node once and performs a constant amount of pointer work per visit: one temporary assignment, one link reversal, and two pointer advances. It uses only prev, current, and temp, regardless of the list length.

Complexity analysis

• Time: O(n), because all n nodes are processed once.
• Space: O(1) auxiliary space, because the algorithm stores only a fixed number of pointers.
• Output structure: The original nodes are reused; no values or nodes are copied.

Micro-example For four nodes, there are four iterations and four link flips. For ten thousand nodes, there are still only three working references; the number of references does not grow with n.

Pitfalls

• O(1) space refers to auxiliary memory, not the input list itself.
• A recursive solution has O(n) call-stack space, so it does not meet the constant-space target.
• Linear time is necessary because every link must be redirected.

Recap

• Save the successor, reverse one link, and advance.
• Return prev after current becomes null.
• Final target: O(n) time and O(1) extra space.