题解 | #孩子们的游戏(圆圈中最后剩下的数)#

递归法（重点是想到局部处理，具体处理方案是其他思考，如下）

对残缺的链表我们很难处理，因此每次去除一个我们都把它处理成完整的链表（这次去除的链表节点后的每个位置都往前移动一位），这样我们就得到了新的少一位的完整链表。

虽然改变了名称，但是去除的实际节点并没有改变，那么我们只需要找到这些实际节点在没有移动的链表中的位置。

需要注意顺序是从短到长，也就是虽然最短为1时它的坐标是当前链表中的0，但是它通过多次转换到最初长n的链表中的位置是第一个m，也就是(m-1)%n的。(m-1)的思路是m的位置实际是m-1。

到要取的第二、第三到第n个节点依次增长，得到的是那么长链表的最后一个取出节点在当前链表中的位置。

设第r次取出的节点位置为x，在它现在的链表中，下一个位置是y=(x+m)%n; 注意这里的n不是总的n，而是当前链表的总长度，这个y也是在第r次链表中的位置。 我们要得到y位置在以它为最后一个取出节点的链表中的位置（这也是我们题目想要的），它相对第r次的链表只长了一个节点。

设第r+1次的长度为n。 在第r+1次链表中取出的这个节点如果在x的前面，那么x对应的实际值应该+1，如果在后面那么这个x的值就不变。 如果在前面说明越过了，那么因为新的链表更长一格，所以到新的轮回中的前面会短一个，结果上和(x+m)%n是一样的。 如果在后面那么还不到n-1，除出来的结果(x+m)%(n-1)和(x+m)%n也是一样的。 所以我们的递推公式用(x+m)%n就好。

我们不需要知道太久远的回忆，只要知道第r+1次取出的节点在当时的链表中的位置就可以了，而它是用第r次的链表算出来的。 这样一次一次算下去就可以得到最终结果。 链接

public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int LastRemaining_Solution(int n, int m) {
        // write code here
        //因为题目说了n是大于等于1的，所以这里没有进行检查，只是递归出口
        if(n==1) return 0;
        int x = LastRemaining_Solution(n-1, m);
        return (x+m)%n;
    }
};