Reverse a linked list: keep the unprocessed suffix reachable

Draw identities, not just values

A node is an object; next is a reference to another object, not its value. Two nodes with equal values are still different queue entries. A baseline can push node references onto a stack, pop them, and reconnect in reverse order: O(n) time and O(n) auxiliary space. Copying only values into new nodes would violate the identity contract. To remove the stack, keep three references: the reversed prefix, the current node, and its saved successor.

At the start of each iteration, previous heads the already reversed prefix and current heads the untouched suffix. Together they contain each original node exactly once, with no link from the prefix into the suffix. Save current.next before redirecting it to previous; then move previous to current and current to the saved successor. Losing the successor first makes the suffix unreachable. The two regions still partition the original nodes, and one node moves from suffix to prefix. When current is None, the whole chain is reversed and previous is the new head.

The reference first checks shape and uses slow/fast pointers to reject cycles, then mutates. This extra pass preserves the “no partial mutation on invalid input” contract while retaining O(n) total time and O(1) auxiliary space. The output is only a reference; existing nodes are not counted as new storage. Recursive reversal is elegant but uses O(n) call-stack space and can exceed Python's recursion limit on a deep chain.

Watch the saved successor arrive before the link changes, then follow the two variable references as they advance. The node objects stay in place.

Follow-up 1: reverse only an interior segment

Predict the links that must be repaired outside the reversed region. For the inclusive node segment b through d, both attachment points matter:

Save predecessor, old segment head, and the node after the segment before rewiring. The old segment head becomes its tail. Validate positional bounds before mutation if failure must leave the original list intact. A dummy head simplifies a segment that starts at position zero.

Follow-up 2: readers retain old next-link behavior

The same node cannot simultaneously have its old and new next through one field. Copying introduces O(n) new storage and new identities; an indirection layer needs version semantics. A senior candidate tests identity, tail termination, and reversing twice. A lead candidate settles mutation ownership and publication before adding locks or promising stable readers; the local routine has no concurrency protocol.

Run and check

From the repository root:

cd curriculum/01-code/02-data-structures-algorithms/problems/14-reverse-linked-list
python -m unittest -v test_solution.py

Reference implementation (download file, source below) · Contract and oracle tests (download file, source below). Read the tests after your attempt. A green reference suite verifies the supplied implementation; it does not demonstrate independent transfer. Reimplement one follow-up with the reference closed and explain which old invariant no longer holds.

from dataclasses import dataclass

@dataclass(eq=False)
class Node:
    value: object
    next: "Node | None" = None

def _next(node):
    if node is None:
        return None
    if not isinstance(node, Node) or (node.next is not None and not isinstance(node.next, Node)):
        raise ValueError("links must be Node objects or None")
    return node.next

def reverse_list(head):
    slow = fast = head
    while fast is not None:
        fast = _next(_next(fast))
        slow = _next(slow)
        if fast is not None and slow is fast:
            raise ValueError("input must be acyclic")
    previous, current = None, head
    while current is not None:
        following = current.next
        current.next = previous
        previous, current = current, following
    return previous

import unittest
from solution import Node, reverse_list

class ReverseTests(unittest.TestCase):
    def test_identity_and_involution(self):
        for size in [0, 1, 2, 3, 10000]:
            nodes = [Node(7) for _ in range(size)]
            for left, right in zip(nodes, nodes[1:]):
                left.next = right
            head = nodes[0] if nodes else None
            reversed_head = reverse_list(head)
            current = reversed_head
            for expected in reversed(nodes):
                self.assertIs(current, expected)
                current = current.next
            self.assertIsNone(current)
            self.assertIs(reverse_list(reversed_head), head)
            self.assertTrue(all(node.next is (nodes[i+1] if i+1 < size else None)
                                for i, node in enumerate(nodes)))

    def test_invalid_input_is_not_partially_mutated(self):
        a, b, c = Node(1), Node(2), Node(3)
        a.next, b.next, c.next = b, c, b
        with self.assertRaises(ValueError):
            reverse_list(a)
        self.assertIs(a.next, b)
        self.assertIs(b.next, c)
        self.assertIs(c.next, b)
        c.next = 42
        with self.assertRaises(ValueError):
            reverse_list(a)
        self.assertIs(a.next, b)
        self.assertEqual(c.next, 42)
        a.next = a
        with self.assertRaises(ValueError):
            reverse_list(a)
        with self.assertRaises(ValueError):
            reverse_list("bad")

if __name__ == "__main__":
    unittest.main()