Linked List Pointer Rewiring

Tactic

Linked-list pointer rewiring changes node links without array indexing. The tactic is to keep stable handles to the nodes before, inside, and after the region being changed.

The invariant is that no live part of the chain is lost. Before overwriting a next pointer, store the node you still need to reach.

Dummy nodes reduce edge cases because the head becomes an ordinary node after dummy. For reversal, swapping, and deletion, name the predecessor and successor before modifying links.

Value

The value is doing structural edits in place. Arrays require shifting elements, but linked lists can splice nodes by changing references.

Direct complexity example

Brute force: Copy list values into an array, transform them, then rebuild links: $O(n)$ time and $O(n)$ space.
With this tactic: Rewire nodes directly in one pass: $O(n)$ time and $O(1)$ extra space.
Space: Some problems still need a map for random pointers or cache lookup, which raises space to $O(n)$ .

Challenges this solves

reverse linked list
swap nodes in pairs
reverse nodes in k group
remove nth from end
reorder list
LRU cache lists

When to use it

Use this tactic when these conditions are true:

the input is a linked list
the task changes node order or removes nodes
node identity matters more than values
the desired solution asks for constant extra space

When not to use it

Reach for a different tactic when these warning signs appear:

random access by index is needed repeatedly
the list is immutable
copying values is allowed and much simpler for the constraints
extra cross-links require a hash map

Terminology clues

These prompt words often point toward this concept:

linked list
reverse
swap nodes
remove node
reorder
dummy node
next pointer
in-place