Solution: Counting Around a Circular List

Suppose we have a Node class defined like this:

class Node {
  int value;
  Node next;

  Node(int value) {
    this.value = value;
  }
}

First, we build the circle:

Node first = new Node(0);
Node last = first;
for (int i = 1; i < n; i++) {
  last.next = new Node(i);
  last = last.next;
}
last.next = first;  // close the circle

With n = 6, the circle looks like this. The current reference is for the counting, which I describe next.

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

We need to unlink the k-th person counted. Since the nodes are singly linked, unlinking a node requires a reference to the node before it. So we keep current one node before the count: current is the node before the person where the count starts. Then the person counted 1 is current.next, the person counted 2 is current.next.next, and so on. After moving current forward k - 1 times, current.next is the k-th person counted, and we unlink it.

Here is the first elimination with n = 6 and k = 3. The count starts at person 0, so current begins on person 5, the node just before, which is what the picture above shows. Person 0 is counted 1 and person 1 is counted 2, which moves current forward twice, onto person 1:

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

Now current.next is person 2, the third counted, and one assignment unlinks them:

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

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

After the unlinking, current.next is the person right after the eliminated one, which is exactly where the count resumes. In other words, current is again the node before the start of the count, so the next round works the same way.

Here is the full method:

public static int survivor(int n, int k) {
  // build the circle of n people
  Node first = new Node(0);
  Node last = first;
  for (int i = 1; i < n; i++) {
    last.next = new Node(i);
    last = last.next;
  }
  last.next = first;  // close the circle

  // the count starts at person 0, so we stand just before them
  Node current = last;
  int alive = n;
  while (alive > 1) {
    for (int counted = 1; counted < k; counted++) {
      current = current.next;
    }
    current.next = current.next.next;  // unlink the k-th person counted
    alive--;
  }
  return current.value;
}

When the loop ends, only one node is left, and current refers to it. That is because current only ever refers to a node that is still in the circle. The circle of one is also handled correctly: the last unlinking makes current.next point to current itself.

You can check the method against n = 6 and k = 3. The eliminations happen in the order 2, 5, 3, 1, 4, and the survivor is 0. Person 2 was eliminated above. The count resumes at person 3: persons 3 and 4 are counted 1 and 2, and person 5, the third counted, is unlinked:

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

The count wraps around to person 0: persons 0 and 1 are counted 1 and 2, and person 3 is eliminated:

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

Next the count starts at person 4: person 4 is counted 1, person 0 is counted 2, and person 1 is eliminated:

   ┌───┐      ┌───┐
┌▶ │ 0 │ ──▶  │ 4 │ ─┐
│  └───┘      └───┘  │
│    ▲               │
│    │               │
│ current            │
└────────────────────┘

With two people left, the count starts at person 4, passes person 0, and comes back to person 4, who is counted third and eliminated. That leaves the circle of one, with person 0 pointing at itself:

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

The special cases are also handled correctly. With n = 1, the build makes a single node pointing to itself, the loop never runs, and person 0 is returned. With k = 1, the inner loop never runs, so current stays in place and the method unlinks current.next again and again: people are eliminated in order, and person n - 1 is the last one left.

What does this cost? Each elimination follows $k-1$ links and does one unlinking, all $O(1)$ steps, so an elimination is $O(k)$. With $n-1$ eliminations, the total is $O(nk)$, the same as the queue solution. The difference is that the code matches the game more directly. The nodes stay in place and current moves around the circle. Eliminating a person is one assignment, and there is no rotation of the queue.