Python linked-list reversal: validate cycles before changing links

Operation contract

The program first walks the chain, rejecting a cycle or more than 64 nodes before it changes any link. It then saves each successor, points the current node at the previous node and advances. The caller receives the new head; the former head is now the tail. These are the same node objects, so every external alias still refers to its original node.

Failure and ownership boundary

The validation set uses extra memory to guarantee rejection before mutation. Claiming constant extra storage for this whole operation would therefore be wrong, even though the pointer-replacement phase alone uses three references. Concurrent mutation and objects that override attribute access are outside this fixture’s contract. Python shallow and deep copies: preserve aliases deliberately does not describe this in-place ownership change.

Working program

class DispatchNode:
    def __init__(self, receipt_id, next_node=None):
        self.receipt_id = receipt_id
        self.next = next_node

def reverse_chain(head):
    seen, current = set(), head
    while current is not None:
        if type(current) is not DispatchNode or id(current) in seen or len(seen) == 64:
            raise ValueError("cycle, node type or chain budget")
        seen.add(id(current)); current = current.next
    previous, current = None, head
    while current is not None:
        successor = current.next
        current.next = previous
        previous, current = current, successor
    return previous

head = DispatchNode(41, DispatchNode(42, DispatchNode(43)))
old_head = head
head = reverse_chain(head)
values = []
while head is not None:
    values.append(head.receipt_id); head = head.next
print(values)
print(old_head.next is None)

Output

[43, 42, 41]
True

Costs and limits

Two passes give O(n) work. Cycle/budget validation stores O(n) identities; pointer replacement itself has O(1) temporary reference storage.

Common Mistakes

• Retain the successor before replacing the next reference.
• Describe validation memory rather than claiming the complete safe operation is constant-space.

Connected lessons

Python variables: names refer to objects, assignment does not copy, Python shallow and deep copies: preserve aliases deliberately, Python iterative tree traversal: shared nodes are not a tree, Java LinkedList: operations, internals and failure cases.