In-Place Manipulation of a Linked List — How the Pattern Works
In-Place Manipulation of a Linked List restructures singly and circular linked lists directly by mutating .next pointers without allocating auxiliary arrays or duplicate nodes. Every link update preserves reachability through the atomic three-step sequence — save nxt = curr.next, rewire curr.next, and advance pointers — combined with sentinel (dummy) nodes when the head may change and two-pointer offsets for middle or tail discovery. This eliminates O(n) extra node/array memory and O(n^2) repeated traversals, executing reversals, deletions, splits, and interleavings in O(n) time and O(1) auxiliary space.
- Input is the head of a singly or circular linked list and the prompt mandates O(1) extra space or forbids modifying node .val fields and allocating new nodes.
- Prompt asks to reverse an entire list, a [left, right] slice, fixed k-node groups, adjacent pairs, or conditional even-length groups.
- Prompt asks to interleave, partition, split, or rotate a linked list by position (e.g., L_0 -> L_n -> L_1 -> L_{n-1}, odd-even positions, rotate right by k, split into k parts).
- Prompt asks to remove duplicate values, filter matching elements, delete m-keep/n-drop runs, or splice a node into a sorted circular ring.
- Overwriting curr.next before saving nxt = curr.next, permanently severing the only pointer path to the rest of the linked list.
- Advancing prev immediately after deleting prev.next = prev.next.next — on consecutive target nodes (e.g., [6, 6] or [1, 1, 1]), moving prev skips testing the newly linked prev.next.
- Forgetting to terminate split or rotated list tails with None (such as leaving slow.next connected in Reorder List or omitting new_tail.next = None in Rotate List), creating an infinite pointer cycle.
- Handling head modifications with ad-hoc conditionals instead of prepending dummy = ListNode(0, head) and returning dummy.next, causing null-dereference bugs on empty or single-node inputs.
def reverse_list(head):
prev, curr = None, head
while curr:
nxt = curr.next
curr.next = prev
prev, curr = curr, nxt
return prevdef remove_matching(head, target):
dummy = ListNode(0, head)
prev = dummy
while prev.next:
if prev.next.val == target:
prev.next = prev.next.next
else:
prev = prev.next
return dummy.nextdef reverse_slice_after(prev, moves):
curr = prev.next
for _ in range(moves):
moved = curr.next
curr.next = moved.next
moved.next = prev.next
prev.next = moved