java数组模拟链表解决约瑟夫环

约瑟夫环

约瑟夫环是一个经典的问题。
问题描述：N个人围成一圈，从第一个人开始报数，报到m的人出圈，剩下的人继续从1开始报数，报到m的人出圈；如此往复，直到所有人出圈。（模拟此过程，输出出圈的人的序号）
比如有五个人,编号为1，2，3，4，5每次报数为3的出局
1 2 3 4 5 此时3号出局，从四号开始
1 2 3 4 5 轮到1号出局
1 2 3 4 5 五号出局
最后二号出局，四号胜利。
数组模拟链表的意思是自定义一个对象数组，里面存储的是下一个节点的序号，和前一个节点的序号。
以第一次三号出局为例，此时2的next应该指向4，而4的prev应该指向2,。并且2和4都是通过3的prev和next寻找的。

import java.util.*;
class node{
	int prev;
	int next;
}
//数组模拟双向循环链表解决约瑟夫环
public class Main {
public static node[]ini(node[]a){//初始化数组
	for(int i=0;i<a.length;i++) {
		a[i]=new node();
	}
	for(int i=1;i<a.length;i++) {
		a[i].next=i+1;
		a[i].prev=i-1;
		if(i==a.length-1)a[i].next=1;
		if(i==1)a[i].prev=a.length-1;
	}
	return a;
}
public static int joseph(node[]a,int num) {//核心代码
	int i=1,count=0;
	while(i!=a[i].next) {
		System.out.println("i= "+i+" node.prev= "+a[i].prev+" node.next= "+a[i].next);
		count++;
		if(count==num) {
			count=0;
			int prevnode=a[i].prev;
			int nextnode=a[i].next;
			a[nextnode].prev=prevnode;
			a[prevnode].next=nextnode;
		}
		i=a[i].next;
	}
	return i;
}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()) {
			int people=sc.nextInt();
			int num=sc.nextInt();
			node[]peo=new node[people+1];
			//为了方便编号，以peo[1]作为第一个元素
			peo=ini(peo);
			System.out.println(joseph(peo,num));
		}
	}

}