【java版数据结构】死亡游戏约瑟夫避免自杀问题

介绍： 有一天罗马人占领了犹太人的领地，39个犹太人与约瑟夫以及他的朋友躲 到一个山洞中，39个犹太人决定宁愿死也不要被罗马人招降，于是它们决定了一个自杀方式，41个人排成一个圆圈，第一个人从1开始报数，依次往后，如果有人报到3，那么这个人就必须自杀，然后由他的下一个人重新从1开始报数，直到所有人都自杀身亡。然而约瑟夫和他的朋友并不想遵从，于是约瑟夫要他的朋友先假装遵从，他将朋友与自己安排在第16与第31个位置，从而逃过 了这场死亡游戏。

问题转换： 41个人围坐一圈，第一个人编号为1，第二个人编号为2…第n个人编号为n 1.编号为1的人开始从1报数，报数为3的那个人退出圈 2.自退出的那个人开始的下一个人再次从1开始报数，以此类推 3.求出最后退出圈的那个人的编号

解题思路:

1.构建含有41个结点的单向循环链表，分别存储1-41的值，分别代表这41个人

2.使用计数器count，记录当前报数的值

3.遍历链表，每循环一次count++

4.假如count==3,则删除当前结点，并打印删除的结点的值，并把count重置为0

重点：用pre和before指针指向了当前结点下一个结点的上一个结点，方便做连接和删除操作

代码：

public class JosephTest {
          
   
    public static void main(String[] args) {
          
   
        Node first=null;
        Node pre=null;
    //1.创建循环链表
        for (int i = 1; i <=41 ; i++) {
          
   
            //创建第一个结点
            if (i==1){
          
   
                first = new Node(i, null);
                //将当前结点变成下一个结点的上一个结点
                pre=first;
                continue;
            }
            //创建中间结点
            Node newNode = new Node(i, null);
            //建立连接
            pre.next=newNode;
            //将当前结点变成下一个结点的上一个结点
            pre=newNode;
            if (i==41){
          
   
                //建立循环
                pre.next=first;
            }
        }
    //2.创建计数器，记录报数结果
        int count=0;
        //记录每次遍历拿到的结点，默认从首结点开始
        Node n=first;
        //记录当前结点的上一个结点，默认从首结点的上一个结点开始null
        Node before=null;
    //3.遍历循环链表
        while(n!=n.next) {
          
   
            //计数器累加
            count++;
            if (count == 3) {
          
   
                // 如果计数到3，删除当前结点,并重置count=0
                before.next = n.next;
                count=0;
                //打印被删除的结点
                System.out.print(n.item + ",");
                n = n.next;
            } else {
          
   
                //将当前结点变成下一个结点的上一个结点
                before=n;
                //如果没有计数到3，则往下移动一位
                n = n.next;
            }
        }
        //打印出剩余到最后的那个人
        System.out.println(n.item);
    }
//内部结点类
    private static class Node<T>{
          
   
        T item;
        Node next;
        public Node(T item, Node next) {
          
   
            this.item = item;
            this.next = next;
        }
    }
}