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

class Solution {
public:
    struct Node{
        int data;
        Node* next;
        Node(int x):data(x), next(nullptr){}
    };
    // 看着题目，套用链表属性
    int LastRemaining_Solution(int n, int m) {
        // write code here
        Node* head = new Node(0);
        Node* cur;
        cur = head;
        for(int i = 1; i < n; ++i)
        {
            Node* tmp = new Node(i);
            cur->next = tmp;
            cur = cur->next; 
        }
        cur->next = head;// 构成一个环
        Node* pre = cur;
        Node* now = head;
        // std::cout << " head : " << now->data << std::endl;
        while (now->next!= now) // 环判断链表元素个数是否为1
        {
            for(int i = 0; i < m-1; ++i)// 由于剔除的是第m个，所以循环m-1次
            {
                //std::cout << now->data << " ";
                pre = now;
                now = now->next;
            }
            // std::cout << std::endl;
            pre->next = now->next;// 剔除第m个元素
            // std::cout << now->data << std::endl;
            now = now->next;
        }
        return now->data;// 最后一个元素就是待返回值
    }
};