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

struct Node{
    int val;
    Node* next;
    Node(int x):val(x),next(nullptr){}
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int LastRemaining_Solution(int n, int m) {
        // write code here
        //https://www.cnblogs.com/nxf-rabbit75/p/10707989.html
        //https://blog.nowcoder.net/n/1578f938852b4c7c87aa3720a940647d?f=comment
        //特殊情况
        if(n<1||n>5000||m<1||m>10000){
            return -1;
        }
        if(n==1){
            return 0;
        }

        //构建环形链表
        Node *head = new Node(0), *front = head;
        for(int len=1;len<n;len++){
            Node *temp = new Node(len);
            front->next = temp;
            front = front->next;
        }
        front->next = head;

        //循环数数，删除节点，直到只剩一个节点
        while(head!=front){
            for(int count=0; count<m-1; count++){
                front = head;
                head = head->next;
            }
            front->next = head->next;
            delete head;
            head = front->next;
        }
        return head->val;
    }
};