单向环形链表应用场景(约瑟夫问题的讲解) java详细讲解
单向环形链表应用场景
约瑟夫问题
Josephu(约瑟夫、约瑟夫环) 问题
Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。
注：丢手帕问题
解题思路
1、新建一个环线链表，实现链表的增查功能
2、设计出圈顺序，使用helper作为辅助指针，协助取消指针引用
代码实现
package com.qf.linkedList;public class Josefu { public static void main(String[] args) { CircleLinkedList circleLinkedList=new CircleLinkedList(); circleLinkedList.add(600); circleLinkedList.list(); circleLinkedList.countBoy(50,20,600); }}class CircleLinkedList{ private Boy first=new Boy(-1); //添加 public void add(int num){ if (num<1){ System.out.println("输入的数据有误，请重试~~~"); return; } Boy curBoy=null; for (int i = 1; i <= num; i++) { Boy boy=new Boy(i); if (i==1){ //第一个元素成为了队头，并循环 first=boy; first.setNext(first); curBoy=first; }else{ boy.setNext(first); curBoy.setNext(boy); curBoy=boy; } } } public void countBoy(int startNo,int countNums,int nums){ //从startNo开始数数 ，countNums表示的是步长，nums代表的是总共的长度 if (first==null||startNo<1||countNums>nums){ System.out.println("输入的数据有误，请重新输入"); } Boy helper=first; //1、找到helper的位置，它在first的前一个位置 while (true){ if (helper.getNext()==first){ break; } helper=helper.getNext(); } //2、让first、helper移动到指定的位置startNo，需要移动startNo-1下 for (int i=0;i<startNo-1;i++){ first=first.getNext(); helper=helper.getNext(); } //3、让小孩报数，移动first和helper的指针,移动countNums-1下 while (true){ if (first==helper){ break; } for (int j = 0; j < countNums-1; j++) { first=first.getNext(); helper=helper.getNext(); } System.out.println("出圈的编号为："+first.getNo()); first = first.getNext(); helper.setNext(first); } System.out.println("组后出圈的编号为："+first.getNo()); } //展示 public void list(){ Boy temp=first; while (true){ System.out.println(temp); if (temp.getNext()==first){ break; } temp=temp.getNext(); } }}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; } @Override public String toString() { return "Boy{" + "no=" + no + '}'; }}