NC132：环形链表的约瑟夫问题：

参考--剑指offer：圆圈中最后剩下的数字
https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/si-chong-fang-fa-xiang-xi-jie-da-by-yuanninesuns/
解法1：数学 + 迭代+递归
反推过程：(当前index + m) % 上一轮剩余数字的个数
最终剩下一个人时的安全位置肯定为1，反推安全位置在人数为n时的编号
人数为1： 0+1
人数为2： (0+m) % 2+1
人数为3： ((0+m) % 2 + m) % 3+1
人数为4： (((0+m) % 2 + m) % 3 + m) % 4+1
........
迭代推理到n就可以得出答案

    public int ysf(int n, int m){
        if (m < 1 || n < 1)
            return -1;
        int last = 0;
        // i代表有目前有个人 
           //最后一轮剩下2个人，所以从2开始反推
        for (int i = 2; i <= n; i++)
            last = (last + m) % i;
        return last+1;
    }

递归

    public int ysf (int n, int m) {
        // write code here
        if(n < 1 || m < 1)       
            return 0;
        if(n == 1)
            return 1;
        return (ysf(n-1,m)+m-1)%n + 1;
    }
}

解法2：链表
将[1,n]依次存储在链表中
只要链表的长度不为1，就一直循环，如果到了第m个就remove；否则将其添加到链表尾部
时间复杂度为O(nm)

public int LastRemaining(int n, int m){
        LinkedList<Integer> list=new LinkedList<>();
        if(m<1 || n<1){
            return -1;
        }
        for(int i=0;i<n;i++){
            list.add(i);
        }
        int bt=0;
        while(list.size()>1){
            bt=(bt+m-1)%list.size();
            list.remove(bt);
        }
        return list.get(0)+1;
    }

解法3：单向链表
转载：https://blog.csdn.net/qq_45702990/article/details/107326453
① 构造单向环形列表
思路：
先创建第一个节点，让 first 指向该节点，并构建成环形
后面每创建一个新的节点，将该节点加入到已有的环形链表中即可
图示：

代码如下：

/**
 * 构建单向环形链表
 * @param nums 队列人数
 */
public void circle(int nums) {
    //数据校验，如果传入的数据不合法，提示并结束方法
    if (nums < 1) {
        System.out.println("nums的值不正确！无法创建环！");
        return;
    }
    //初始化中间节点
    Node temp = null;
    for (int i = 1; i <= nums; i++) {
        //用来存放每次新创建的编号节点
        Node node = new Node(i);
        //如果是第一个节点，则直接赋值给first，且构建成环状
        if (i == 1) {
            first = node;
            first.next = first;
            temp = first;
            continue;
        }
        //如果不是第一个节点，则将其添加进环中
        temp.next = node;
        node.next = first;
        temp = node;
    }
}

② 遍历环形链表
思路：
先让一个辅助节点 temp 指向 first节点
然后通过一个 while 循环遍历该环形链表即可（如果 temp.next==first 则结束循环）
代码如下：

/**
 * 遍历打印环形链表
 */
public void list() {
    //如果第一个节点没有数据，则链表为空，提示并结束方法
    if (first == null) {
        System.out.println("链表为空！");
        return;
    }
    //借助辅助节点遍历
    Node temp = first;
    while (temp.next != first) {
        System.out.println(temp);
        temp = temp.next;
    }
    System.out.println(temp);
}

③约瑟夫环问题解决
思路：
先创建一个辅助节点 temp 指向当前链表的最后一个节点
在开始报数前，先让 temp 与 first 同时移动 k-1 次
当开始报数时，让 temp 与 first 同时移动 m-1 次
将 first 指向的编号出列，first 指向出列节点的下一个节点
图示：

代码如下：

/**
 * 计算约瑟夫环的出列序列
 * @param k 第k个节点开始
 * @param m 开始后第m个节点出列
 * @param n 一共有n个节点
 */
public void joseph(int k, int m, int n) {
    //数据校验，如果数据不合法则提示且结束方法
    if (first == null || k < 1 || k > n) {
        System.out.println("数据不合法！");
        return;
    }
    //辅助节点
    Node temp = first;
  //找到环形链表的最后一个节点（下一个节点为 first 节点的节点），并赋值给辅助节点
    while (temp.next != first) {
        temp = temp.next;
    }
    //在开始报数前，先让 temp 与 first 同时移动 k-1 次
    for (int i = 0; i < k - 1; i++) {
        first = first.next;
        temp = temp.next;
    }
    //当 temp == first 时，环形链表中只剩下一个节点，结束循环
    while (temp != first) {
        //找到报数为 m 的节点
        for (int i = 0; i < m - 1; i++) {
            first = first.next;
            temp = temp.next;
        }
        //输出当前节点编号，且将当前节点出列
        System.out.printf("%d-->", first.id);
        first = first.next;
        temp.next = first;
    }
    //输出最后节点编号
    System.out.println(first.id);
}