总共3中解决方法，1、数学推导，2、使用ArrayList递归解决，3、使用首位相连的LinkedList解决
import java.util.ArrayList;
public class Josephus {
public static void main(String[] args) {
int n = 13;
int k = 3;
int last;
//last =getLast(n,k);//使用数学推导求结果
//System.out.println(last);
MyLinkedList list = new MyLinkedList();
for (int i = 1; i <= n; i++) {
list.add(i);
}
//只要链表中元素个数大于1个，则指向下面步骤
while(list.length>1){
Node temp = list.first;//获得头节点
//将temp节点从头节点向后挪k个位置
for (int i = 1; i < k; i++) {
temp = temp.next;
}
System.out.println("被移除的编号为："+temp.value);
list.remove(temp);//移除当前temp位置的节点
System.out.println("剩余元素为："+list.toString()+",长度为"+list.length);
}
//当上面循环结束时，链表内只剩1个元素
last = list.first.value;
System.out.println(last);
}
public static int getLast(int n , int k){
int last = 1;//这是初始值，即环内为1个人时剩余的人的编号，必然为1，也是后面推导的基础
//System.out.println("当环内有1个人时，剩余的是:1");
for (int i = 2; i <= n; i++) {//当圈内为i个人时，结果是圈内为i-1个人的结果加K后对i求余
last = ((last + k - 1) % i) + 1;//为避免出现结果为0，让i-1的结果先减1，求余后再加1
//System.out.println("当环内有" + i + "个人时，剩余的是:" + last);
}
return last;
}
public static int getLast(ArrayList list, int k , int m){
int last = -1;//用来放置最后一个人的编号
int index = -1;//用来放置当前一轮被移除的人的下标
if (list.size() == 1) { // 如果集合内只剩一个元素，则直接返回该元素作为结果
last = list.get(0);
} else {
index = (m + k - 1) % list.size(); // 求出当前一轮被移除的人的下标
list.remove(index); // 将该人移除
m = index % list.size(); // 求出新一轮报数时开始的人在新集合里的下标
last = getLast(list, k, m); // 使用剩余的集合和m的位置重新开始下一轮计算
}
return last;
}
}
class Node{
Integer value;
Node next;
Node prev;
public Node(){
value = null;
prev=null;
next = null;
}
public Node(Integer value){
this.value = value;
next = null;
prev = null;
}
public String toString(){
return this.prev.value+""+this.next.value;
}
}
class MyLinkedList{
public Node first;
public Node last;
public int length;
public MyLinkedList(){
first = new Node();
last = first;
length = 0;
}
//在链表结尾增加元素的方法
public void add(Integer i){
if(length == 0){
first.value = i;//添加第一个元素，只需要设置该元素的value
}else{
Node temp = new Node();//添加元素时，1、新建一个元素，
temp.value = i;
temp.prev = last;//2、然后先与last节点建立双向关系，
last.next = temp;
first.prev = temp;//3、再与first节点建立双向关系，
temp.next = first;
last = temp;//4、最后让last指向该节点，3、4步可颠倒
}
length++;
}
//从链表中删除指定节点的方法
public void remove(Node node){
node.prev.next = node.next;//将前节点的next跳过本节点，指向下个节点
node.next.prev = node.prev;//将后节点的prev跳过本节点，指向前节点，此时该节点已经从链表中移除了
this.first = node.next;//指定后节点为头节点
this.last = node.prev;//指定前节点为尾节点
node = null;
length--;
}
public String toString(){
String str ="[";
Node temp = first;
for (int i = 1 ; i < length; i++ ) {
str += temp.value+",";
temp = temp.next;
}
str += (temp.value+"]");
return str;
}
}