一.概述
传说有这样一个故事，在罗马人占领乔塔帕特后，39 个犹太人与约瑟夫及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，第一个人从1开始报数，依次往后，如果有人报数到3，那么这个人就必须自杀，然后再由他的下一个人重新从1开始报数，直到所有人都自杀身亡为止。然而约瑟夫和他的朋友并不想遵从。于是，约瑟夫要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，从而逃过了这场死亡游戏 。
解题思路：
1.构建含有41个结点的单向循环链表，分别存储1~41的值，分别代表这41个人；
2.使用计数器count，记录当前报数的值；
3.遍历链表，每循环一次，count++；
4.判断count的值，如果是3，则从链表中删除这个结点并打印结点的值，把count重置为0；
二.代码实现
public class Joseph {
private static class Node<T> {//节点类
T data;
Node next;
public Node(T data,Node next){
this.data=data;
this.next=next;
}
public static void main(String[] args) {
//1.构建循环链表 ※
Node<Integer> head=null;
Node<Integer> pre=null;//记录前一个节点
for(int i=1;i<=41;i++){
if(i==1) { //如果是第一个结点
head = new Node<>(i, null);
pre = head;//更新pre
continue; //跳出本次循环，进入下一次循环
}
//如果不是第一个结点
Node<Integer> newNode = new Node<>(i, null);
pre.next=newNode; //连接结点
pre=newNode; //更新pre，为当前结点
if(i==41){//如果是最后一个结点，让最后一个结点的next为head
pre.next=head;
}
}
//2.需要count计数器，模拟报数
//3.循环遍历链表
int count=0;
Node<Integer> curr=head; //记录当前结点
Node<Integer> before=null;//首结点的前一个为null
while(curr!=curr.next){ //结论：当删到最后一个时，会自己指向自己！
//模拟报数
count++;
//判断当前报数的是不是3
if(count==3){ //如果是3，删除当前结点，打印，重置count，当前结点后移
before.next=curr.next; //连接curr的前后结点即删除curr，before不用动
System.out.print(curr.data+" ");
count=0; //count归零
curr=curr.next; //更新curr向后移一位
}else{
before=curr; //更新before
curr=curr.next; //更新curr向后移一位
}
}
System.out.println("last one:" +curr.data);
}
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89380.html
