Linked Lists - Advanced Topics in Java: Core Concepts in Data Structures - page 105

As shown, child 1 is no longer in the list; the storage for this node would be reclaimed eventually by Java. We
count to 5 again, starting from child 2. The count ends at child 3, which is eliminated by setting child 2's pointer to
point to child 4. The list will look like this:

curr

2 4

Finally, we count to 5 starting at child 4. The count ends at child 4, which is eliminated. Child 2 is the winner.
Note that this solution (as opposed to the array version) really does eliminate a child from the game by deleting
its node. Eliminated children are neither inspected nor counted since they are gone! This is more in keeping with the
way the game is played.
Program P3.7 plays the game and finds the winner using a linked list representation. We keep the solution simple
and faithful to the description of the game. As such, we do not use the LinkedList class. Rather, we use a Node class
with two fields: an int to hold the number of a child and a pointer to the next child.
After getting the number of children and the length of the count-out, the program calls linkCircular to create a
circular linked list of the children and then playGame to eliminate all but one of the children.

Program P3.7

import java.util.*;
public class CountOut {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int m, n;
do {
System.out.printf("Enter number of children and length of count-out: ");
n = in.nextInt();
m = in.nextInt();
} while (n < 1 || m < 1);

Node last = linkCircular(n); //link children in a circular list
Node winner = playGame(last, n-1, m); //eliminate n-1 children
System.out.printf("The winning child: %d\n", winner.num);
} //end main

public static Node linkCircular(int n) {
//link n children in a circular list;
//return pointer to last child; this will point to the first
Node first, np;

first = np = new Node(1); //first child
for (int h = 2; h <= n; h++) { //link the others
np.next = new Node(h);
np = np.next;
}
np.next = first; //set last child to point to first
return np;
} //end linkCircular