AlgoScope

Rewiring a List

algorithmintermediateTime O(n)Space O(1)

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.

12345headtail

Rotate the list right by 2: the last 2 nodes move to the front. No node is moved: close the list into a ring through the tail, then cut the ring at the right place.

Check your understanding

The player pauses before the one decision in this run and asks what happens next. Here it is, with the answer.

  1. Rotating right by 2 on 5 nodes. Which node becomes the new tail?

    • 3
    • 5

    Answer: 3. The new tail is n - k mod n - 1 = 2 steps from the old head.

How it runs, step by step

  1. Rotate the list right by 2: the last 2 nodes move to the front. No node is moved: close the list into a ring through the tail, then cut the ring at the right place.

    Rotating 1, 2, 3, 4, 5 right by 2.

  2. Walk to the tail, counting as you go: the tail is 5 and n = 5.

    Tail 5, length 5.

  3. Point the tail at the head: the list is now a ring, and any node could be its head. Rotating right by 2 means the head should be the node 2 from the end, so the cut goes 3 steps in.

    Tail linked to head, forming a ring.

  4. Walk n - k mod n - 1 = 5 - 2 - 1 = 2 steps from the head to 3: it becomes the new tail, and the node after it, 4, the new head.

    Cut after 3.

  5. Move the head to 4 and cut 3's arrow. The ring is open again and reads 4, 5, 1, 2, 3.

    List reads 4, 5, 1, 2, 3.

  6. Rotated: 4, 5, 1, 2, 3. One pass to find the tail and length, one to find the cut, three arrow changes, O(n) time, O(1) space. Reducing k mod n first keeps a huge k from walking round the ring.

    Result 4, 5, 1, 2, 3.

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

Related

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

Next up