package top.baikunlong.linkedlist; /** * @author baikunlong * @date 2020/10/9 13:22 */ public class Josephus { public static void main(String[] args) { CircleSingleLinkedList list = new CircleSingleLinkedList(); list.countBoy(5,1,2);//2 4 1 5 3 System.out.println(); list.countBoy(5,2,3);//4 2 1 3 5 } } /** * 循环单链表 */ class CircleSingleLinkedList{ private Boy first; public void addBoy(int count){ if(count<1){ System.out.println("最小1"); return; } Boy temp=null; for (int i = 1; i <= count; i++) { Boy boy = new Boy(i, "boy" + i); if(i==1){//如果是第一个,则赋值给first,让它初始化 first = boy; first.next=first;//形成环 temp=first;//临时变量,用于移动指针进行添加 }else { temp.next= boy;//下一个指向最新的boy boy.next=first;//最新的boy的下一个指向first形成环 temp=boy; } } } public void show(){ if(first==null){ System.out.println("空链表"); return; } Boy temp=first; while(true){ System.out.println(temp.toString()); temp=temp.next; if(temp==first)return; } } /** * 报数 * @param n 总共几个人 * @param k 从第几个开始报数 * @param m 数几下 */ public void countBoy(int n,int k,int m){ if(k>n||k<1||m<1){ System.out.println("数据错误"); return; } //重新初始化链表 addBoy(n); //因为是单链表,所以首先需要一个临时指针指向first的前一个,帮助出圈 Boy temp=first; while (true){ if(temp.next==first){ break; }else { temp=temp.next; } } //从第几个开始报数,需要移动指针到开始位置 for (int i = 0; i < k-1; i++) { first=first.next; temp=temp.next; } //开始报数 while (temp!=first){ //移动m-1次,从1开始数的 for (int i = 0; i < m - 1; i++) { first=first.next; temp=temp.next; } //删除 System.out.println("出圈="+first.toString()); first=first.next; temp.next=first; } System.out.println("最后的boy="+first.toString()); } } class Boy{ public int no; public String name; public Boy next; public Boy(int no,String name) { this.no = no; this.name = name; } @Override public String toString() { return "Boy{" + "no=" + no + ", name='" + name + '\'' + '}'; } }