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

图片说明

![image-20200728195456076]([编程题] nk:[二叉搜索树的后序遍历].assets/image-20200728195456076.png)

输入输出

说明:

思路

案例图解:我们以输入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;
    }
}