   # How to solve Josephus Problem using Linked List?

1,203 views

Josephus Problem talks about a problem where there are people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. posted Nov 23, 2013

Assume link list is circular link list, then have two functions like this and call eliminate with the index you want to skip after each execution.

``````public int RemoveAt(int index)
{
int value = 0;
Node current = first;
do
{
if (current.Counter == index)
{
value = current.Data;
}
current = current.Next;
} while (current != first);
return value;
}

public int Eliminate(int m)
{
int value = 0;
Node current = first;
Node nextNode;

do
{
nextNode = current.next;
value = RemoveAt(m);
current = nextNode;

} while (current != first);
return value;
}
`````` answer Nov 23, 2013
Similar Questions