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

The canonical input is the 5-node list 1 -> 2 -> 3 -> 4 -> 5 -> null. Five rewires produce the reversed list 5 -> 4 -> 3 -> 2 -> 1 -> null.

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

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.