Josepfu问题

Josephu问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
例如： n = 5 , 即有5个人
k = 1, 从第一个人开始报数
m = 2, 数2下,则出圈的顺序为： 2->4->1->5->3

• 解决思路：使用单向环形链表解决
• 构造单向环形链表的思路：
  1. 先创建一个节点，让first指向该结点，并让该结点的next指向它自己，这样接形成了一个只有一个就结点的单向环形链
  2. 之后没创建一个新的结点，就把该结点加入到已有的环形链表中
• 遍历环形链表思路：
  1. 先让一个辅助指针变量指向first结点
  2. 然后通过while(true)循环遍历，当curNode.next == first时循环结束
• 结点出圈的思路：
  1. 先创建一个辅助变量helper，默认值为当前链表的最后一个元素，需要通过一次遍历来找到
  2. 让fisrt和helper移动k-1次到达它们应该在的位置
  3. 开始报数，让first和helper结点同时移动m-1次
  4. 此时让first所指向的结点出圈，即first = first.getNext(); helper.setNext(first);而之前的first结点因为没有任何的引用，所以就会被java回收机制回收

代码如下：

public class Josepfu {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.add(5);
        System.out.print("当前链表值为：");circleSingleLinkedList.show();

        //方法参数为 1,2,5 时出圈顺序：2->4->1->5->3
        circleSingleLinkedList.countNode(1,2,5);

    }
}

//创建一个单向环形链表
class CircleSingleLinkedList{
    //创建一个first结点，默认没有编号
    private Node first = null;

    //添加nums个结点，构建一个单向环形链表
    public void add(int nums){
        //对nums做一个校验
        if(nums < 1){
            System.out.println("nums的值不正确");
            return;
        }
        //创建一个辅助变量，来帮助我们构建单向环形链表
        Node curNode = null;
        //创建链表
        for (int i = 1; i <= nums; i++) {
            //根据当前编号i来创建结点
            Node node = new Node(i);
            if(i == 1){  //如果是第一个结点，则让它指向它自己
                first = node;
                first.setNext(first); //构成一个只有一个节点的环
                curNode = first; //让当前结点指向first结点
            }else {  //如果不是第一个结点，则将新创建的结点加到环形链表的最后
                curNode.setNext(node);
                node.setNext(first);
                curNode = node;
            }
        }
    }

    //遍历当前环形链表
    public void show(){
        //判断当前链表是否为空
        if(first == null){
            System.out.println("当前链表为空。。。");
            return;
        }
        //因为first结点不能动，所以创建一个辅助结点帮助遍历
        Node curNode = first;
        //如果不为空，则开始遍历单链表
        while (true){
            System.out.print(curNode.getNo() + ",");
            if(curNode.getNext() == first){ //当curNode.getNext() == first时则表明单向环形链表一次循环已经结束
                break;
            }
            curNode = curNode.getNext(); //当前结点向后移
        }
    }

    /**
     * 根据用户的输入，计算出结点出圈的顺序
     * @param startNo 表示从第几个结点开始数数
     * @param countNum 表示数几下
     * @param nums 表示最初共有多少个结点
     */
    public void countNode(int startNo, int countNum, int nums){
        //对数据进行校验
        if(first == null || startNo < 1 || startNo > nums){
            System.out.println("输入的数据有误");
            return;
        }
        //需要一个辅助结点，指向当前结点的前一个结点，用于结点的删除,
        //helper初始值应为first结点的前一个，通过下面的while循环得到
        Node helper = first;
        while (true){
            if(helper.getNext() == first){
                break;
            }
            helper = helper.getNext();
        }
        //在进行报数之前，让first和helper向后移动（K-1）次，即（startNo - 1） 次，
        // 让first和helper到达指定位置
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        //开始报数，报数时让first和helper同时移动m-1次，然后将该结点出圈
        while (true){
            if(helper == first){ //当圈中只有一个节点的时候退出循环
                System.out.println("\n最后一个出圈的结点是： " + helper.getNo());
                break;
            }
            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //输出当前要出圈的first结点的值
            System.out.print("\n出圈的结点是： " + first.getNo());
            //first 结点出圈（删除当前的first结点）
            first = first.getNext();
            helper.setNext(first);
        }
    }
}

//创建一个Node类，表示一个结点
class Node{
    private int no; //编号
    private Node next; //下一个节点，默认为null

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

    public int getNo() {
        return no;
    }

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

    public Node getNext() {
        return next;
    }

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

运行结果：