题解 | #孩子们的游戏(圆圈中最后剩下的数)# 环形链表的约瑟夫问题

class Solution {
public:
      struct ListNode {
      int val;
      ListNode *next, *pre;
      ListNode(int x) : val(x), next(NULL), pre(NULL) {}
  };
    
    int LastRemaining_Solution(int n, int m) {
 // step1: build一个环形链表 0 - n-1
        ListNode *head = new ListNode(0);
        ListNode *pre, *curr, *next;
        curr = head;
        pre = nullptr;
        
        int count = 0;
        while(count < n - 1) {
            count++;
            ListNode *node = new ListNode(count);
            curr->next = node;
            node->pre = curr;
            curr = curr->next;
        }
        curr->next = head;

    
        // step2 : 在链表内做算法
        int index = 1;
        curr = head;
        ListNode *prev= curr;

        while(curr->next != curr) {
            if (++index == m) {
                curr->next = curr->next->next;
                index = 1;
            }
            curr = curr->next;
        }
        // 返回值
        return curr->val;
        // write code here
        
    }
};