Linked List Interview Questions: Prove Pointer Changes With Mutation Traces

Two linked lists can print the same values and still contain different nodes. A reversal can look plausible while losing its suffix. A splice can produce the right receiver while the donor container still points into the transferred nodes. A printed value sequence can hide the exact node you lost or replaced.

For linked list interview questions, make each pointer change reviewable: name the node identities, save the edge you are about to overwrite, and check the resulting reachable nodes and endpoints. This guide works through reversal, deletion, and donor transfer using one small Python model.

Evidence boundary: language behavior comes from official Python documentation; structural background comes from the author’s Open Data Structures. The exercises, contracts, traces, and recommendations are original PracHub material. The accompanying original fixture executed 29 named scenarios on CPython 3.12.14; its saved result records their names and scope. They check single-threaded in-memory behavior, not production performance, garbage-collection timing, or company question frequency. Linked PracHub records are individual practice prompts, not a forecast of your interview.

Start with C++ Code Reading: Bug in a Linked-List insertAfter and Predicting Polymorphic Output. Its insertion problem asks the same useful question: what happened to the node that used to follow the insertion point?

Define identity and the list contract first

Our initial chain is A(7) → B(7) → C(9) → None. Letters name objects; parentheses contain payload values. A and B are different objects even though both store seven. Python’s data model distinguishes identity from value; is compares identity.

from dataclasses import dataclass

@dataclass(eq=False)
class Node:
    label: str
    value: int
    next: 'Node | None' = None

@dataclass(eq=False)
class Chain:
    head: Node | None = None
    tail: Node | None = None

The debug label is not an ownership system. We use eq=False so generated field-by-field equality does not turn our node checks into value comparisons; see the official dataclasses documentation. Comparing the actual references catches a replacement node even if it copies both the debug label and payload.

Declare these exercise invariants: traversal reaches None without visiting an object twice; an empty chain has both endpoints None; otherwise, tail is the last reachable node and tail.next is None. Operations preserve payload values. Reversal and deletion assume a valid acyclic chain whose links the caller is entitled to change.

The SLList chapter in Open Data Structures explains head/tail bookkeeping and why removing the final element needs special treatment. Our extra identity and donor-transfer contracts make those obligations directly testable.

Reverse a list without losing the unprocessed suffix

Before overwriting cur.next, save it. After the overwrite, following cur.next takes you backward through the reversed prefix; it no longer reaches the unprocessed suffix.

def reverse(chain):
    old_head = chain.head
    prev, cur = None, chain.head
    while cur is not None:
        following = cur.next
        cur.next = prev
        prev, cur = cur, following
    chain.head, chain.tail = prev, old_head

The loop invariant has two parts: prev starts the already reversed prefix, and cur starts the unprocessed suffix. Together they retain every original node exactly once. The saved following reference lets the next iteration continue into that suffix.

The new head is C and the new tail is A. An external variable that previously pointed to A still points to A; it now refers to the tail. Reversal changes links and container endpoints, not every variable held by the caller.

Our negative control deliberately overwrites cur.next before using it to advance. Only A remains reachable from the returned reference. A bounded identity scan detects the missing B and C. This counterexample explains why assignment order matters more clearly than “use three pointers.”

The algorithm uses O(n) time and O(1) auxiliary references. A test scan that records every visited node uses O(n) space; keep that separate from the implementation’s space claim. The code assumes acyclic input. Adding cycle detection or a policy for cyclic lists changes the contract and requires its own tests.

Delete the requested object, then repair the endpoints

“Delete a node” is underspecified. Do you remove the first matching value, every matching value, or one exact object? Here the target is a node reference, and a foreign object holding seven must leave the chain unchanged.

def delete_identity(chain, target):
    prev, cur = None, chain.head
    while cur is not None:
        if cur is target:
            if prev is None:
                chain.head = cur.next
            else:
                prev.next = cur.next
            if chain.tail is cur:
                chain.tail = prev
            cur.next = None
            return True
        prev, cur = cur, cur.next
    return False

Deleting B from A → B → C changes A.next to C, then detaches B by setting its next link to None. The receiver contains A and C; a caller holding B can no longer traverse from B into C. Detachment is our chosen API behavior, not an automatic consequence of unlinking a node.

Deleting A changes the head to B. Deleting C changes the tail to B. Deleting the only node makes both endpoints None. A second deletion of the same removed object returns False. State those outcomes before choosing an implementation shortcut.

The “copy the next node’s value and bypass it” trick implements a different contract. It cannot handle the tail that way, and it changes which object carries which payload. If the caller asked to remove B’s identity, leaving B alive with C’s value is not equivalent.

Our implementation searches for the predecessor, so deletion costs O(n) time and O(1) auxiliary space. Having a pointer to the target does not provide its predecessor in a singly linked list. If an API already supplies a valid predecessor, the unlink itself can be constant work; checking that predecessor may still require traversal.

Splice a donor without creating two apparent owners

Receiver: A → B → C. Donor: D → E. Insert the donor after A and transfer its nodes to the receiver. The expected result is A → D → E → B → C, while the donor container becomes empty.

Save B before changing A’s outgoing edge. Connect A to D, connect E to B, and clear the donor’s head and tail. Because the insertion is internal, the receiver tail stays C. If insertion occurs after C instead, E becomes the receiver tail.

The nonempty mutation core below runs after validation. dst and src are distinct containers, both valid and disjoint, src is nonempty, and anchor is reachable in nonempty dst.

following = anchor.next
anchor.next = src.head
src.tail.next = following
if dst.tail is anchor:
    dst.tail = src.tail
src.head = src.tail = None

Clearing the donor prevents that container from continuing to advertise the transferred chain. It does not invalidate other Python references to D or E. Ownership here means the intended container responsibility; Python does not enforce exclusive node ownership for this class.

Our checked wrapper scans both inputs before any write. It rejects a self-donor, shared reachable nodes, cycles, inconsistent tails, and an anchor outside the receiver. An empty receiver requires anchor=None and adopts the donor endpoints directly. An empty donor is a no-op after validation. The wrapper therefore takes O(n+m) time and space, even though its accepted pointer rewiring uses constant work.

Why reject overlap? Suppose the receiver is A → B → C and the supposed donor is a second container starting at B. Treating it as an independent chain can reconnect nodes into a cycle or duplicate the intended ownership. An intersection of the two identity sets finds this before mutation. Equal payloads in separate nodes are allowed; shared objects are the problem.

If an interviewer guarantees valid, disjoint lists and a valid anchor, say that an unchecked mutation helper can rely on those preconditions. Do not quietly remove validation and keep claiming that arbitrary input is safe.

Test reachable identities, not just printed values

A useful test oracle must stop on a cycle rather than hanging while trying to print the broken result:

def nodes(head):
    seen, result = set(), []
    while head is not None:
        if head in seen:
            raise ValueError('cycle')
        seen.add(head)
        result.append(head)
        head = head.next
    return result

For an expected sequence of actual references, compare lengths, then each pair with is. Check head and tail against the first and last expected references, and verify the tail’s outgoing link. Python’s unittest assertion reference also provides assertIs for identity assertions.

Execution result: 29 named scenarios passed on CPython 3.12.14, including negative controls that must detect the intended defect. The count describes this small fixture, not exhaustive coverage. Reversing twice is useful, but it is insufficient alone: a no-op implementation also returns to its original state. For A/B/C, check the intermediate C/B/A identities before checking the round trip back to A/B/C.

For rejected splices, we snapshot endpoints and existing links before the call, then compare them afterward. That checks the promised failure behavior. It does not establish transactional rollback under memory exhaustion or concurrent mutation. For accepted transfers, an empty donor and the expected receiver identities establish this exercise’s container contract.

Choose the next question by the contract it adds

Practice the changed requirement explicitly. A remove-all-values prompt is different from deleting one object; a range replacement adds two boundaries; cyclic overlap removes our acyclic precondition.

Continue with Replace a Range of Nodes in a Linked List with Another Linked List. Before coding, draw the prefix, removed range, donor, and suffix. Then name the exact identities expected in the result and explain which references remain valid. Use that trace to explain which assignments must change when the removed range includes the head or tail.

Sources and Further Reading

• Python 3.12 data model — objects, values, and types: identity, mutability, and references.
• Python 3.12 dataclasses: generated equality and the eq option.
• Pat Morin, Open Data Structures — SLList: singly linked nodes and endpoint maintenance.
• Python 3.12 unittest — assertIs: assertions comparing object identity.