方法一：朴素模拟法 O(m*n)

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n<=0 || m<=0)return -1;
        ListNode head = new ListNode(0);
        ListNode p = head;
        for(int i=1; i<=n-1; ++i){
            ListNode node = new ListNode(i);//串成链
            p.next = node;
            p = p.next;
        }
        p.next = head;//p回到开头位置的前一个，形成闭环
                      //还有一个作用是，让p指向head前一个开始，可以使每轮循环一样套路
        for(int i=1; i<=n-1; ++i){
            for(int j=1; j<=m-1; ++j){
                p=p.next;
            }
            p.next = p.next.next;//java会自动回收，所以不管那个被删除的节点
        }
        return p.val;//剩下的最后一个
    }
}//这种思路是：模拟完整的游戏运行机制，不跳步
//时间O(m*n) 空间O(n)

方法二：数学归纳法 O(n) [分析是难点]

public class Solution {
    public int LastRemaining_Solution(int n, int m) {//时光倒流递推法:为什么要逆向？因为逆向是由少到多不会有空位；而正向会有空位，必须模拟、不能跳步
        if(n<=0)return -1;
        int res = 0; //f(1,m)=0
        for(int i=2; i<=n; i++){//i就是小朋友数量，i=2是游戏最后一轮，但是我解法的第一轮 //循环从i=2到i=n，小朋友越来越多，此解法是倒推（时光倒流）
            res = (res + m) % i;  //相邻项关系：左边res是f(n,m) 右边res是f(n-1,m)
        }
        return res;
    }
}//时间O(n) 空间O(1)

数学归纳法分析：

数学归纳法：
f(n,m)表示：【相对参考系：从0位置开始，最终到达f(n,m)位置】//例如：从0开始，最终到达f(5,3)=3的位置
f(1,m)=0;//首项
f(n,m)=[(m%n) + f(n-1,m)]%n;//公式化简为：f(n,m)=[m + f(n-1,m)]%n //相邻项关系【重点，推导如下】:
例如：
f(5,3)=[f(4,3)+ 3%5 ] %5=f(4,3)+3 什么意思？
f(5,3)从0开始，0-1-2，删除2节点，然后来到3==》这时的情况就类似f(4,3)。但还有一点不一样,就是标准的f(4,3)从0开始，而这里从3开始
f(4,3)根据定义，必须从0开始（所有的f(i,m)的定义需要一致），而不是从3。所以必须进行【对齐操作】：
于是f(5,3)的参靠系里：先走3步，然后以3为起点，走f(4,3)步 ==》f(5,3)=3+ f(4,3) [这里是简化，再考虑%n的细节优化下就ok了]
有了递推公式，用递归法or迭代法，求解都几乎同理
迭代法：f(1,m)=0 f(2,m)=[m + f(1,m)]%n ... 一直算到f(n,m)