单链表——约瑟福问题

解题思路:

构建一个单向的环形链表思路

1.先创建第一个节点，让First指向该节点，并形成环形

2.后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可。

遍历环形链表

1.先让一个辅助指针(变量)curBoy，指向First节点

2.然后通过一个while循环遍历该环形链表即可，结束条件curBoy.next=first

根据用户的输入，生成一个小孩出圈的顺序

1.需要创建一个·辅助指针(变量)helper，事先应该指向环形链表的最后节点            第一个人可省略补充：小孩报数前，先让first和helper移动从哪个人开始-1次

2.当小孩报数时，让first和helper指针同时移动m-1次

3.这时可以将first指向的小孩节点出圈 

first=first.next

helper.next=first

注意事项:

参考代码:

import java.util.Scanner;

public class Main{
   public static void main(String[] args) {
       Scanner scanner=new Scanner(System.in);
       int a=scanner.nextInt();
       CircleLinkedList circleLinkedList=new CircleLinkedList();
       circleLinkedList.add(a);
       circleLinkedList.countBoy(a);

  }

}
class CircleLinkedList{
  private Boy first=new Boy(-1);
   //添加操作
   public void add(int nums){
       if (nums <= 0) {
           System.out.println("无效的参数");
           return;
       }
       Boy curBoy=null;
       for (int i=1;i<=nums;i++){
         Boy boy=new Boy(i);
         if (i==1){
             first=boy;//第一个节点
            first.setNext(first);//将链表闭环
            curBoy=first;//更新辅助指针
         }else {
             curBoy.setNext(boy);//保持连接性
             boy.setNext(first);//闭环
             curBoy=boy;//更新
         }
       }
   }
   public void countBoy(int nums){

     //判断条件不可少
       if (first == null||1>nums) {
           System.out.println("链表为空");
           return;
       }
       Boy helper=first;
       while (true){
           if (helper.getNext()==first){//到达最后一个节点
               break;
           }
           helper=helper.getNext();
       }
       //此时已获取最后一个节点

//这里因为只从第一个人开始数数，所以可以省略

       //因为题目要求我们是从第一个小孩开始数数
       while (true){
           if (helper==first){//说明圈中只有一个人
               break;
           }
           for (int i=0;i<2;i++){//让first指向目标结点的前一个节点，而curBoy指向first的前一个节点
               first=first.getNext();
               helper=helper.getNext();
           }
           first=first.getNext();
           helper.setNext(first);
       }
       System.out.println(first.getNo());
   }
}

class Boy{
   private int no;
   private Boy next;

   public Boy(int no) {
       this.no = no;
   }

   public int getNo() {
       return no;
   }

   public void setNo(int no) {
       this.no = no;
   }

   public Boy getNext() {
       return next;
   }

   public void setNext(Boy next) {
       this.next = next;
   }
}