Linked list rewiring
Overview
Techniques for safely changing the `next` pointers of linked list nodes to achieve complex structural changes in O(1) space.
It is the core mechanic behind all intermediate and advanced linked list interview questions.
Where used: In-place memory defragmentation, Functional programming list manipulation
Why it exists
Problem: We need to deeply manipulate the structure of a linked list (like reversing sublists, swapping nodes in pairs, or rotating). Re-creating the list wastes O(n) memory.
Naive approach: Copy the values into an array, manipulate the array, and build a new linked list.
Better idea: Manipulate the `next` pointers of the existing nodes directly in-place. Use a dummy head to handle edge cases easily.
Why learn this
- Pointer manipulation is a fundamental skill in systems programming (C/C++).
- It rigorously tests your attention to detail and edge cases (like null pointers).
Mental model
It's like unhooking train cars and hooking them up in a different order while the train is still on the tracks.
Rewiring requires tracking multiple adjacent nodes (prev, curr, next). We carefully sever a `next` pointer and point it elsewhere, but we must save a reference to the severed tail first, or we lose the rest of the list.
Repeated decision: Have I saved the reference to the next node before overwriting my current node's next pointer?
Deep dive
Rewiring a linked list is a dance of temporary variables. If you want node `A` to point to node `C` instead of `B`, you can write `A.next = C`. But if no other variable points to `B`, node `B` (and the rest of the list) is lost in memory. The golden rule of rewiring is: **always grab a reference to the next node before you break the link**.
For complex operations like Reversing a Sublist or Swapping Nodes in Pairs, we frequently use a `dummy` node. A dummy node is a fake head (`dummy = Node(0, head)`) that guarantees the list always has a node before the actual head. This eliminates the need for special `if head == target` branches when rewiring affects the first element.
When reversing a sublist (from position `m` to `n`), we first traverse to the node right before `m` (let's call it `prev`). Then, we do a standard reversal for `n - m` steps. Finally, we reconnect the broken ends: `prev` points to the new head of the reversed sublist, and the old head of the sublist points to the node right after `n`.
Key points
- Dummy Head: Always use a dummy head when the operation might change the head of the list. It turns edge cases into standard cases.
- Temporary Pointers: You almost always need `prev`, `curr`, and `nxt` pointers to safely rewire without orphans.
Pattern: Pointer Rewiring (Dummy Head)
Recognition cues:
- Modify a linked list in-place
- Reverse parts of a list
- Swap adjacent nodes
Failure signals
- You are using a `while` loop but getting a `NoneType has no attribute 'next'` error.
Engineering examples
OS Memory Management
Managing blocks of free memory.
Free lists are often implemented as linked lists. Allocating and merging blocks involves complex rewiring of pointers.
When not to use
- When read access speed is prioritized over memory: If you need fast random access during the rewiring logic, copying to an array might be better in real systems, though it fails the O(1) space constraint of interviews.
Common mistakes
- Losing the rest of the list: Overwriting `curr.next` before storing `curr.next` in a temporary variable orphans the remainder of the list, leading to a memory leak or wrong answer.
- Null pointer exceptions: Trying to access `curr.next.next` without first checking if `curr` and `curr.next` are not `None`.
Recall questions
- Why is a dummy head node useful in linked list rewiring?
- What is the golden rule of breaking a `next` pointer?
Understanding checks
If you write `curr.next = prev`, then `prev = curr`, then `curr = curr.next`, what happens to the traversal?
It goes backwards or enters an infinite loop.
You just set `curr.next` to point backwards to `prev`. When you do `curr = curr.next`, you travel back to the node you just came from. You forgot to save the *original* `curr.next`.
What is the space complexity of reversing a sublist of length M in a linked list of length N?
O(1) space.
We only use a few constant pointers (prev, curr, nxt), regardless of the length of the list.
Questions & answers
Swap Nodes in Pairs
Use a dummy head. Iterate in steps of 2, rewiring `prev.next`, `curr.next`, and `nxt.next`.
Approach: Draw out the 3 pointers before coding. Save `curr.next.next`.
Practice tasks
Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes.
Continue learning
Previous: Traversal & reversal