[编程题] nk：[约瑟夫问题（孩子们的游戏-圈内最终剩余的人的编号

[编程题] nk：约瑟夫问题（孩子们的游戏-圈内最终剩余的人的编号）

输入输出

说明：

思路

案例图解：我们以输入n=5,m=3为例：

解释：

（一开始自己错的地方是在如下，while退出条件的地方，错写为dummy.next!=head为退出条件，其实我们本质是要检测圈中剩下一个节点，也就是dummy的next还是dummy我们就退出！）

Java代码

public class Solution {
    //思路：模拟循环链表的方法
    public static int LastRemaining_Solution(int n, int m) {
        //极端条件
        if (n <= 0) {
            return -1;
        }
        //步骤1:创建一个由n个同学组成的循环链表
        Node head = new Node(0);
        Node cur = head;
        for (int i = 1; i < n; i++) {
            cur.next = new Node(i);
            cur = cur.next;
        }
        //把链表的首尾相连
        cur.next = head;

        Node dummy = head;
        int k = 0;
        Node pre = new Node(-1);
        pre.next = dummy;
        while (dummy.next!=dummy){  //这里判断是否是最后一个节点的中止条件是dummy.next!=dummy,而不是dummy.next!=head;
            if(k++ == m-1){
                pre.next = dummy.next;
                dummy = dummy.next;
                k=0;
            }else{
                pre = dummy;
                dummy = dummy.next;
            }
        }
        return dummy.val;

    }
}

class Node{
    int val;
    Node next;
    public Node(int val){
        this.val = val;
    }
}