Rewiring a List
A linked list is nothing but arrows, so rearranging one never means moving data: it means deciding which arrows to change and in what order, without losing hold of a node. Reversing in groups is the plain reversal walk applied k nodes at a time, plus one hook-up per group. Rotating is easiest if you stop thinking of a list as a line: close it into a ring, and the rotation is just choosing where to cut. Reordering as first, last, second, second-last splits the list in the middle, reverses the back half and weaves the halves together. All three are O(n) time and O(1) space, and the nodes never leave their places on screen so every changed arrow is visible.
Reorder the list as first, last, second, second-to-last and so on, in place. Three moves: find the middle with slow and fast pointers, reverse the second half, then weave the two halves together one node at a time.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 4, with their answers.
With 7 nodes, where does slow stop when fast can no longer jump two?
Answer: 4. Slow ends on the last node of the first half, so the halves split evenly or the first half is one longer.
first is 1, second is 7. After this step, what follows 7?
Answer: 2. second is spliced between first and first's old successor.
first is 2, second is 6. After this step, what follows 6?
Answer: 3. second is spliced between first and first's old successor.
first is 3, second is 5. After this step, what follows 5?
Answer: 4. second is spliced between first and first's old successor.
How it runs, step by step
Reorder the list as first, last, second, second-to-last and so on, in place. Three moves: find the middle with slow and fast pointers, reverse the second half, then weave the two halves together one node at a time.
Reordering 1, 2, 3, 4, 5, 6, 7.
Slow moves one node for every two of fast. Fast stops at 7, so slow is at 4: the first half is 1, 2, 3, 4, the second 5, 6, 7.
Middle at 4.
Cut the first half off after 4, then reverse the second half: 5 now points at null.
5 points at null.
6 now points at 5.
6 points at 5.
7 now points at 6.
7 points at 6.
Second half reversed, its front is 7. Now weave: take one node from the first half, then one from the second, until the second half runs out.
Weaving from 1 and 7.
1 points at 7, and 7 points at 2, where the first half continues. Next pair: 2 and 6.
1 then 7.
2 points at 6, and 6 points at 3, where the first half continues. Next pair: 3 and 5.
2 then 6.
3 points at 5, and 5 points at 4, where the first half continues. The second half is used up, so the weave is done.
3 then 5.
Reordered: 1, 7, 2, 6, 3, 5, 4. Middle by fast and slow, reverse the back half, weave: three linear passes and no extra memory, O(n) time, O(1) space.
Result 1, 7, 2, 6, 3, 5, 4.
Remember
- Reverse in groups: count k ahead first, flip the group's arrows with prev and curr, then hook the previous group's tail onto the new front.
- Rotate right by k: walk to the tail, link it to the head to make a ring, cut n - k mod n steps in.
- Reorder: middle by slow and fast, reverse the second half, weave first and second alternately until the second half runs out.
Topics covered
Where this is used
Operating systemsKernel object lists
Linux keeps almost everything, from the list of every task in the system to the memory-reclaim LRU lists, on circular doubly linked lists built from a struct list_head embedded inside the object itself. Because the links live in the object, moving an entry from one list to another is list_move: a handful of pointer writes with no allocation and no copying, which is what makes it usable in paths that are not allowed to fail or block. list_rotate_left is this lesson's ring trick kept permanently closed, so rotation never needs a cut at all.
NetworkingNetwork packet buffers
A packet moving through a network stack is a chain of buffers, mbufs on BSD and sk_buffs on Linux, not one contiguous block. When a layer needs room for a header and the current buffer has none in front, M_PREPEND links a fresh mbuf onto the head of the chain rather than copying the payload into a larger allocation, and fragmenting or joining a segment means cutting the chain and relinking it. That is much of what zero copy means in practice: the bytes stay put, only the arrows change.
Memory managementAllocator free lists
glibc's malloc parks freed chunks on doubly linked bins. When a chunk is released next to one that is already free the allocator merges them, and the first step is splicing the neighbour out of its bin by writing fd->bk and bk->fd past it, exactly the unlink you do when dropping a node here. Getting it wrong is worse than a broken list: the classic unlink attack feeds the allocator forged fd and bk values and turns that one relink into an arbitrary memory write.
RuntimesCollectors with no stack to spare
Tracing an object graph normally needs an explicit stack, but a garbage collector runs precisely when memory has run out and cannot allocate one. The Deutsch-Schorr-Waite algorithm reverses each pointer as it descends, so the path back to the root is stored inside the objects it has already visited, then restores every arrow on the way back up. It is the prev, curr and next dance from this lesson applied to a graph instead of a line.
Why it works this way
Why count k ahead before changing a single arrow
Reversing is destructive: once a group's arrows point backwards you can no longer walk forward to find out how many nodes were really there. The probe loop asks "are there k left?" while the list is still intact, so a short final group can be recognised and left alone. It also leaves probe sitting on the first node of the next group, which the reversal itself needs.
Why prev starts at the next group, not at null
In a plain full reversal prev starts null, because the old head really does become the end of the list. Here the group's old front becomes that group's tail and has to point at whatever follows it, so prev is seeded with probe and the join happens as part of the reversal itself, leaving the list walkable end to end after every group. The loop also repairs that same link on the next pass, with tail.next = prev for a full group or tail?.next = start for a short one, so either mechanism on its own would be enough. The bug is having neither: copy the plain reversal, start prev at null and drop the repair, and the list ends after the first k nodes with everything past them unreachable.
Where the cut lands, and why the ring has to be opened again
The new head sits k mod n nodes from the end, which is n - k mod n steps from the old head, so the walk stops one short of that and lands on the new tail. Reducing k by n first is what stops a k larger than the list from walking off the end, and it also makes a k that is a multiple of n land back on the original head. Then cut.next = null is not optional. Skip it and you are left with a valid circular list, so the next length count, print or comparison spins forever with nothing pointing at the mistake.
Reorder: the two halves have to actually come apart
slow.next = null is what stops the front half from still pointing into the back half. Leave it out and, once the weave hooks them together, a node ends up pointing at itself or back into the middle, so you have built a cycle instead of a reordering. The slow and fast loop as written leaves the front half the longer one on odd lengths, and that is what lets the weave stop cleanly when second runs out: if the back half were the longer one the loop would run on after first had already reached the end, and dereference null.
Read more
- Linked listWikipedia
- List management functionsLinux kernel documentation · docs.kernel.org
- include/linux/list.hLinux kernel source · git.kernel.org
- queue(7): list and tail queue macrosman7.org
- mbuf(9): network packet buffer chainsFreeBSD