package heap;
public class Josephus {
public static int f(int n, int m) {
int i;
Link x,t;
t = new Link();
t.setKey(1);
x = t;
i = 2;
while( i <= n) {
t.setNext(new Link());
t = t.getNext();
t.setKey(i);
i++;
}
t.setNext(x);
while(t != t.getNext()) {
i = 1;
while(i < m) {
t = t.getNext();
i++;
}
//x = t.getNext(); // This is to free x later
t.setNext(t.getNext().getNext());
}
return t.getKey();
}
}
class Link {
private int key;
private Link next;
public Link() {
next = null;
}
public void setKey(int key) {
this.key = key;
}
public int getKey() {
return key;
}
public void setNext(Link next) {
this.next = next;
}
public Link getNext() {
return next;
}
}
|