Reverse a Singly Linked List

Walk the list with three pointers (prev, cursor, nxt). Save the forward link, flip cursor.next to point backward, then advance both pointers. The new head is prev when cursor reaches None.

Algorithm

Basic Implementation

basic.py

class Node:
    __slots__ = ("value", "next")
    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt

n5 = Node(5)
n4 = Node(4, n5)
n3 = Node(3, n4)
n2 = Node(2, n3)
head = Node(1, n2)

prev = None
cursor = head
while cursor is not None:
    nxt = cursor.next
    cursor.next = prev
    prev = cursor
    cursor = nxt
head = prev

The three-pointer loop saves the forward link, flips one next pointer, then advances prev and cursor.

Step 1 - Save the first forward link

prev starts at null, cursor is node(1), and nxt saves node(2).

Step 2 - Flip node(1)

Set node(1).next to prev, making the reversed prefix 1 -> null.

Step 3 - Reversed prefix reaches 3

After three flips, the prefix is 3 -> 2 -> 1 -> null and cursor is node(4).

Step 4 - Done

When cursor reaches null, prev is the new head: 5 -> 4 -> 3 -> 2 -> 1 -> null.

Complexity

Time: O(n)
Space: O(1)

Implementation notes

Python: do not allocate a new list. The reverse happens in place by flipping next pointers.
The replay shows prev, cursor, nxt plus the "reversed prefix" / "remaining suffix" view at every step, matching the lesson spec.

three-pointer rewire Each iteration captures the forward link, reverses one edge, then steps.