Solution: The Circularly Linked List

In Chapter 6, we ran head.next.next.next.next = head, pointing the last node of a list back at its head, and we said that this creates a circular linked list.

   ┌───┐      ┌───┐      ┌───┐      ┌───┐
┌▶ │ 0 │ ──▶  │ 1 │ ──▶  │ 2 │ ──▶  │ 3 │ ─┐
│  └───┘      └───┘      └───┘      └───┘  │
└──────────────────────────────────────────┘

Then, in the Chapter 6 practice, we wrote an algorithm to detect whether a linked list contains a cycle. In both cases, we did not use the cycle for anything. In the first, it was just something we could build with links. In the second, it was a bug that would make a traversal run forever. For the Josephus problem, we actually want a cycle, since the people in the game stand in a circle.

We need two operations for the Josephus problem.

The first is moving around the circle. To move one position, follow the link: current = current.next. Suppose current is at node 0:

   ┌───┐      ┌───┐      ┌───┐      ┌───┐
┌▶ │ 0 │ ──▶  │ 1 │ ──▶  │ 2 │ ──▶  │ 3 │ ─┐
│  └───┘      └───┘      └───┘      └───┘  │
│    ▲                                     │
│    │                                     │
│ current                                  │
└──────────────────────────────────────────┘

After current = current.next, it is at node 1:

   ┌───┐      ┌───┐      ┌───┐      ┌───┐
┌▶ │ 0 │ ──▶  │ 1 │ ──▶  │ 2 │ ──▶  │ 3 │ ─┐
│  └───┘      └───┘      └───┘      └───┘  │
│               ▲                          │
│               │                          │
│            current                       │
└──────────────────────────────────────────┘

Notice that the nodes stay where they are, and only our reference changes.

The second is removing a node. To remove the node after current, link around it:

current.next = current.next.next;  // unlink the node after current

Continuing from the picture above, current is at node 1, so this removes node 2:

   ┌───┐      ┌───┐                 ┌───┐
┌▶ │ 0 │ ──▶  │ 1 │ ─────────────▶  │ 3 │ ─┐
│  └───┘      └───┘                 └───┘  │
│               ▲                          │
│               │                          │
│            current                       │
└──────────────────────────────────────────┘

                         ┌───┐
                         │ 2 │   (no longer linked)
                         └───┘

This is one assignment, so it is $O(1)$. Note that this removes the node after current, not current itself. Each node stores only a next reference, so to remove a node we need a reference to the node before it.

How do we traverse a circle? In an ordinary linked list, we follow links until we reach null. Here, nothing is ever null, so a loop that stops at null will run forever. Instead, we remember where we started and stop when we return to that node:

Node walker = current;
do {
  System.out.println(walker.value);
  walker = walker.next;
} while (walker != current);

We use a do-while loop because the check must come after the visit: at the start, walker == current is already true, so a regular while loop would end before visiting any node.