Module 11 · Linked Lists and Pointer Mutation

102. Reverse a Linked List

Foundation · Download this solution · All solutions and shared helpers

Problem

Reverse a finite acyclic singly linked list by changing next links, and return the new head. Reuse the existing nodes; do not reverse by copying values into a separate array. None returns None.

Examples

Example 1

list_values(reverse_list(build_list([1,2,3])))
=> [3, 2, 1]

The original nodes are linked in reverse order.

Example 2

reverse_list(None)
=> None

Both regions are initially empty.

Example 3

list_values(reverse_list(build_list([9])))
=> [9]

A singleton remains its own head and tail.

Reveal the worked solution and reasoning

Why this mechanism works

Changing current.next destroys the route to the unread suffix unless it is saved first. Maintain a reversed prefix and an original-order suffix. Transfer one node from the suffix to the front of the prefix at each step.

State and boundaries

previous is the head of the reversed consumed prefix. current is the head of the unread suffix. following temporarily preserves its next node.

Protocol

Initialize previous=None and current=head.
Save current.next.
Point current.next to previous.
Advance previous to current.
Advance current to the saved following node.
Return previous.

Visualization

reversed prefix <- previous | current -> unread suffix
save following; reverse one arrow; advance both
None <- 1 <- 2 <- 3

Python implementation

from structures import build_list, list_values

def reverse_list(head):
    previous, current = None, head
    while current is not None:
        following = current.next
        current.next = previous
        previous = current
        current = following
    return previous

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

list_values(reverse_list(build_list([1,2,3])))

L4 reverse_list: previous, current = None, head
head=N1(val=1,next=N2,random=None); previous=None; current=N1(val=1,next=N2,random=None)

L6 reverse_list: following = current.next
head=N1(val=1,next=N2,random=None); previous=None; current=N1(val=1,next=N2,random=None); following=N2(val=2,next=N3,random=None)

L7 reverse_list: current.next = previous
head=N1(val=1,next=None,random=None); previous=None; current=N1(val=1,next=None,random=None); following=N2(val=2,next=N3,random=None)

L8 reverse_list: previous = current
head=N1(val=1,next=None,random=None); previous=N1(val=1,next=None,random=None); current=N1(val=1,next=None,random=None); following=N2(val=2,next=N3,random=None)

L9 reverse_list: current = following
head=N1(val=1,next=None,random=None); previous=N1(val=1,next=None,random=None); current=N2(val=2,next=N3,random=None); following=N2(val=2,next=N3,random=None)

L6 reverse_list: following = current.next
head=N1(val=1,next=None,random=None); previous=N1(val=1,next=None,random=None); current=N2(val=2,next=N3,random=None); following=N3(val=3,next=None,random=None)

L7 reverse_list: current.next = previous
head=N1(val=1,next=None,random=None); previous=N1(val=1,next=None,random=None); current=N2(val=2,next=N1,random=None); following=N3(val=3,next=None,random=None)

L8 reverse_list: previous = current
head=N1(val=1,next=None,random=None); previous=N2(val=2,next=N1,random=None); current=N2(val=2,next=N1,random=None); following=N3(val=3,next=None,random=None)

... 1 intermediate state changes omitted ...

L6 reverse_list: following = current.next
head=N1(val=1,next=None,random=None); previous=N2(val=2,next=N1,random=None); current=N3(val=3,next=None,random=None); following=None

L7 reverse_list: current.next = previous
head=N1(val=1,next=None,random=None); previous=N2(val=2,next=N1,random=None); current=N3(val=3,next=N2,random=None); following=None

L8 reverse_list: previous = current
head=N1(val=1,next=None,random=None); previous=N3(val=3,next=N2,random=None); current=N3(val=3,next=N2,random=None); following=None

L9 reverse_list: current = following
head=N1(val=1,next=None,random=None); previous=N3(val=3,next=N2,random=None); current=None; following=None

Result: [3, 2, 1]. The original nodes are linked in reverse order.

reverse_list(None)

L4 reverse_list: previous, current = None, head
head=None; previous=None; current=None

Result: None. Both regions are initially empty.

Why the solution is correct

The saved link preserves all unread nodes before mutation. Redirecting one link prepends exactly the current node to the reversed prefix. These disjoint regions still contain all original nodes; when the suffix is empty, previous heads the complete reversal.

Time and space

O(n) time and O(1) auxiliary space.

Common mistakes

Advancing through current.next after overwriting it follows the reversed prefix instead of the unread suffix. Returning the original head returns the new tail.

Reasoning card

State: previous is the head of the reversed consumed prefix. current is the head of the unread suffix. following temporarily preserves its next node.

Invariant: The processed prefix is fully reversed and ends at previous.

Decision to rehearse: Save next, reverse link, advance previous/current.

Finish: Return previous

Transfer exercise

Reverse twice and verify that both the values and original node identities return to their initial order.