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

class Solution {
public:
    //用环形单链表转化为约瑟夫环问题
    struct node{
      int data;
        node* next;
    };
    int LastRemaining_Solution(int n, int m) {
        if(n==1){
            return 0;
        }
        node* head=new node;
        
        head->data=0;
        head->next=NULL;
        node* p=head;
        for(int i=1;i<n;i++){
            node* s=new node;
            s->data=i;
            s->next=NULL;
            p->next=s;
            p=p->next;
        }
        p->next=head;//构成环状链表
        node* pre=p;
        node* cur=head;
        while(cur->next!=cur){//当链表中只剩下一个节点时，循环结束
            
            for(int i=1;i<m;i++){
                pre=cur;
                cur=cur->next;
            }
            //删掉这个节点
            pre->next=cur->next;
            cur=pre->next;
            
        }
        return cur->data;
        
        
        
        
    }
};