孩子们的游戏

这其实就是一个约瑟夫环问题。这里我们可以利用环形链表+模拟的方式解决该问题。我们先构建出一个环形链表，接着开始模拟，其实从0数到m-1就是m次，我们遍历环形链表，每当计数器 == m了，我们就删除对应位置的节点，接着计数器置0，重新开始遍历，直到只剩一个节点。

class Solution
{
    struct ListNode
    {
        int _val;
        struct ListNode* _next;

        ListNode(int val)
            :_val(val)
            , _next(nullptr)
        {}
    };

public:
    // 环形链表模拟
    int LastRemaining_Solution(int n, int m)
    {
        ListNode* head = new ListNode(0);
        ListNode* tail = head;
        for (int i = 1; i < n; ++i)
        {
            ListNode* newnode = new ListNode(i);
            tail->_next = newnode;
            tail = newnode;
        }
        tail->_next = head; // 形成环形链表

        int count = 0;
        ListNode* cur = head;
        ListNode* prev = nullptr;
        while (cur->_next != cur)
        {
            if (++count == m)
            {
                ListNode* next = cur->_next;
                delete cur;
                prev->_next = next;
                cur = next;
                count = 0;
            }
            else
            {
                prev = cur;
                cur = prev->_next;
            }
        }


        return cur->_val;
    }
};