Reverse, splice, and rewire lists in place with careful pointer bookkeeping and a dummy head.
What linked list manipulation is
Rewiring next pointers to reorder, merge, or delete nodes in place - no new nodes, O(1) extra space. The entire skill is pointer bookkeeping: at every step you must be able to say which nodes you still hold references to, because the moment you overwrite a next pointer, anything only reachable through it is gone.
Three moves cover nearly everything: in-place reversal (the prev/curr walk), the dummy head (a sentinel node before the real head so the head case stops being special), and gap runners (two pointers a fixed distance apart, for nth-from-end problems).
How to recognize it
The input is a linked list and the ask is structural: reverse it (wholly, partially, or in k-groups), merge sorted lists, remove the nth node from the end, reorder, rotate, partition, or detect structure. If the answer requires index arithmetic or random access, arrays win; lists win when the operation is splicing.
A second recognition layer: design problems that need O(1) insertion and deletion in the middle - LRU cache being the canonical one, pairing a doubly linked list with a hash map.
The in-place reversal template
Walk the list with two pointers, prev and curr. At each node: save curr.next, point curr.next back at prev, then advance both. When curr runs off the end, prev is the new head. Every partial-reversal problem (reverse between positions, reverse in k-groups, reorder list) is this loop plus careful stitching of the reversed section's endpoints back into the rest - the stitching is where the bugs live, so name the four boundary nodes before coding.
pseudocode
prev = null, curr = head
while curr:
next = curr.next # save before overwriting
curr.next = prev # reverse the arrow
prev = curr # advance
curr = next
return prev # new head
The dummy head
Any operation that might modify or remove the first node - deletion by value, merging, partitioning - gets cleaner with a sentinel: dummy.next = head, operate uniformly, return dummy.next. It converts 'if the head is affected' special cases into the general case. Cost: one local node. When an interviewer sees head-handling if-branches, they are watching you not know this trick.
Common pitfalls
Overwriting a next pointer before saving what it pointed to - the list's tail evaporates. 'Save next first' is the whole discipline.
Losing the new head or returning the old one after reversal - the answer is prev, not head.
Off-by-one in gap runners: for nth-from-end deletion, the lead pointer starts n+1 ahead of the trailer (from a dummy) so the trailer stops at the node before the target.
Cycle creation in reorder/rotate problems: after splicing, terminate the tail explicitly (tail.next = null) or traversals never end.
Skipping the drawing. Serious candidates sketch three nodes and the pointer moves before typing - it is faster than debugging.
Worked examples
1. Reverse a linked listeasy
Reverse a singly linked list in place and return the new head.
Recursion works but costs O(n) stack; the iterative prev/curr walk is O(1) space and is the version to have cold.
Initialize prev = null, curr = head. The invariant: everything before curr is already reversed and prev is its head.
Each step: stash curr.next, point curr.next at prev, slide prev and curr forward one node.
Loop ends when curr is null; prev holds the new head. Rehearse this until it is muscle memory - it is a building block inside harder problems, not just a question.
pseudocode
prev = null, curr = head
while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev
Remember: Maintain the invariant 'prev heads the already-reversed prefix' and the loop body writes itself - save, flip, advance.
2. Merge two sorted listseasy
Merge two sorted linked lists into one sorted list by splicing their nodes together.
This is the merge step of merge sort, on pointers. A dummy head removes the 'which list provides the first node' special case.
Keep a tail pointer at the merged list's end; repeatedly attach the smaller of the two current nodes and advance that list.
When one list is exhausted, attach the remainder of the other in one assignment - no loop needed, it is already sorted and linked.
Return dummy.next. O(n + m) time, O(1) space. This routine is the inner loop of merge-k-lists; get it airtight.
pseudocode
dummy = Node(); tail = dummy
while l1 and l2:
if l1.val <= l2.val: tail.next = l1; l1 = l1.next
else: tail.next = l2; l2 = l2.next
tail = tail.next
tail.next = l1 if l1 else l2
return dummy.next
Remember: A dummy head plus a tail pointer turns merging into one uniform loop - and the leftover list attaches in a single assignment.
3. Remove Nth node from the endmedium
Delete the nth node from the end of a singly linked list in one pass and return the head.
One pass forbids 'count, then walk length - n'. Instead run two pointers with a fixed gap: when the leader reaches the end, the trailer is at the target distance from it.
Deletion needs the node before the target, and the target might be the head - both problems dissolve with a dummy: start both pointers at dummy, advance the leader n+1 steps.
March both pointers together until the leader is null; the trailer now sits just before the victim.
Splice: trailer.next = trailer.next.next; return dummy.next. O(n) time, O(1) space, head deletion included free.
pseudocode
dummy = Node(next=head)
lead = dummy, trail = dummy
repeat n+1 times: lead = lead.next
while lead:
lead = lead.next
trail = trail.next
trail.next = trail.next.next
return dummy.next
Remember: A fixed gap between two runners converts 'nth from the end' into 'when the leader finishes' - and the dummy makes head-removal unexceptional.
Check yourself
Try to answer before revealing - retrieving from memory is what makes it stick.
1In iterative reversal, why must curr.next be saved before it is overwritten?
To keep the loop O(n)
✓ Because it is the only reference to the rest of the list - overwriting it first strands every following node
To handle empty lists
Because prev needs it
A singly linked list is reachable only forward. curr.next is the sole handle on the unprocessed suffix; flip the arrow before saving it and the suffix is garbage-collected out from under you.
2What problem does a dummy (sentinel) head solve?
It makes the list doubly linked
✓ It removes special-case code for operations that might affect the first node, by guaranteeing every real node has a predecessor
It speeds up traversal
It prevents cycles
Deleting or inserting at the head otherwise needs its own branch since nothing precedes it. With dummy.next = head, the head becomes an ordinary node and you return dummy.next at the end.
3For one-pass nth-from-end removal starting both pointers at a dummy, how far ahead should the leader start?
n - 1 steps
n steps
✓ n + 1 steps
It doesn't matter
With a gap of n+1, when the leader hits null the trailer sits at the node before the target - exactly where you must be to splice it out of a singly linked list.
4After merging two sorted lists, one list still has nodes left. What is the right move?
Loop over the remaining nodes, attaching one by one
✓ Attach the entire remainder with a single tail.next assignment
Reverse the remainder first
Copy the remaining values into new nodes
The leftover list is already sorted and internally linked; one pointer assignment splices all of it. Looping is harmless but shows the splice wasn't understood.
Frequently asked questions
Should I practice the recursive or iterative reversal?
Both, but the iterative version is the workhorse: O(1) space and the sub-routine inside reverse-in-k-groups, reorder-list, and palindrome checks. The recursive version is worth knowing to discuss stack costs.
How do I avoid losing nodes during complex rewiring?
Name every node you will need before mutating anything (prevA, curr, nextB...), draw the before/after picture, and write the assignments in an order where nothing needed later is overwritten earlier. If a step count exceeds what you can hold, use more named temporaries - they are free.
Why do LRU-cache designs use a doubly linked list?
The cache must move an arbitrary node to the front and evict from the back in O(1). Doubly linked nodes can unlink themselves without walking from the head, and the paired hash map provides O(1) lookup of the node to move.