Linked Lists and Pointer Ownership

A reference is access to the rest of the list

A singly linked node stores a value and a next reference. Two nodes may have equal values without being the same object. Saving only a value cannot preserve access to a node or its successor.

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

Inserting or deleting next to a known predecessor can require constant link changes. Finding that predecessor can still take O(n). Deleting a singly linked tail without its predecessor is not generally the same operation.

A dummy node makes head changes ordinary

A dummy node precedes the real result. tail starts there; writing tail.next is then the same operation for the first and later outputs. Return dummy.next, not the dummy itself.

dummy = ListNode()
tail = dummy
# Attach accepted nodes through tail.next.
# Advance tail after each attachment.
return dummy.next

This function-body scaffold supports merging, partitioning, deleting and constructing lists. The dummy's value is irrelevant unless the algorithm accidentally includes it. One extra node is constant auxiliary space, not zero allocations.

Save, rewire, then advance

Before each iteration, previous heads the reversed processed prefix, while current heads the unprocessed forward suffix. Save current.next before overwriting it. Otherwise, the only path to the suffix may disappear.

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

This function reuses the original nodes and changes their links. The input is a finite acyclic singly linked list. Empty input returns None; a single node retains next=None. On a cyclic input, this proof does not apply: establish the input contract or detect the cycle first.

Relative motion locates a middle or cycle

Move slow by one and fast by two while fast and fast.next exist. For an acyclic list, this locates a middle. With both starting at the head and that loop guard, an even-length list selects the second middle; a different guard can deliberately select the first.

def has_cycle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

For a cycle of length λ, once both pointers are inside it, fast gains one position on slow per iteration modulo λ. They eventually meet. Compare node identity, not equal values. The null guards prevent an invalid dereference on an acyclic suffix.

If the prefix before the cycle has length μ, a meeting after t slow steps satisfies t≡0 modulo λ. Reset one pointer to the head and move both by one; after μ steps they meet at the entrance. The proof assumes the links stay fixed throughout traversal.

Intersection is shared identity

Two acyclic singly linked lists intersect only when they share an actual node and therefore its fixed successor suffix. Matching values do not establish an intersection.

A length-alignment method advances the longer list by the length difference, then compares identities in parallel. Another switches each traversal to the other head at its end so both cover equal combined distances. Cyclic lists need a separate definition and algorithm; do not silently apply the acyclic argument.

A copied list with random references needs an original-node→new-node map, or an interleaving algorithm with permission to mutate and then restore the original links. Copying next pointers alone leaves random references attached to the original graph.

A moving tail joins sorted components

For two disjoint acyclic lists sorted by value, attach the smaller current head, advance that source pointer, then advance tail. Once one source ends, attach the remaining suffix. A ≤ tie rule selects the first input on ties and preserves its within-list order.

def merge_two_lists(a, b):
    dummy = ListNode()
    tail = dummy
    while a is not None and b is not None:
        if a.value <= b.value:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a if a is not None else b
    return dummy.next

This reuses nodes and changes their links. If inputs share a suffix, naive destructive merging can create cycles or duplicate logical ownership; state disjointness or use a method designed for sharing. Forgetting to advance tail can overwrite a result link.

Merging k lists introduces selection among heads, often a heap or divide-and-conquer merges. The moving-tail invariant remains useful, but the total cost is not simply one two-list scan.

Split before reversing and weaving

Reordering a list can be decomposed into finding a split, detaching the second half, reversing it, then alternately weaving nodes. Detaching prevents old links from creating a cycle during the weave. Save both next references before each pair of link writes.

Checking a palindrome can compare the first half with a reversed second half. If the API promises a nonmutating check, reverse and reconnect afterward even when a mismatch is found. Early returns must not bypass restoration.

A dummy plus a fixed gap can remove a node counted from the end: advance the leading pointer by the validated gap, then move both until the predecessor is located. Define out-of-range behavior. Digit-list addition instead carries arithmetic state, not just a pointer gap.

What constant extra space excludes

Constant reference workspace does not erase node/output storage. An iterative algorithm can still lose nodes or form a cycle; a space bound is not a correctness proof.

Account for every live partial list

Before any node.next write, ask: where is the old successor saved, which partial list now contains this node, what are all current heads/tails, and how will I reach the unfinished suffix?

Test empty, one-node and two-node inputs; even/odd lengths; duplicate values with distinct identities; head/tail removal; and shared or cyclic input when those are in scope. Validate resulting identity coverage and termination, not only the printed values.

Read/write array pointers → preserve unread positions; linked-list rewiring preserves references. Explicit deferred-work stacks → offer another way to represent traversal state when constant auxiliary space is not required.

Related mechanisms

Selecting among multiple list heads → · Traversal order and deferred work →

The reversal frames show exact graph states, not benchmark timings or a garbage-collector simulation. The small functions use the node definition above; value equality never substitutes for node identity.