题解 | #环形链表的约瑟夫问题#

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    struct ListNode{
        int val;
        ListNode* next;
        ListNode(int v){
            val = v;
            next = nullptr;
        }
    };
    
    ListNode* createList(int n){		//创建一个从1到n的环形链表
        ListNode* head = new ListNode(1);
        if(n == 1)
            return head;
        ListNode* rear = head;
        for(int i = 1;i < n; i++){
            rear->next = new ListNode(i+1);
            rear = rear->next;
        }
        rear->next = head;
        return head;
    }
    
    int ysf(int n, int m) {   
        // write code here
        ListNode* head = createList(n);
        ListNode* cur = head,* cur_pre = nullptr;
        while(cur->next != cur){		//开始做约瑟夫问题，当节点的下一节点为自己时，即仅剩最后一个节点，游戏结束
            for(int i = 1; i < m; ++i){
                cur_pre = cur;
                cur = cur->next;
            }
            //删除节点
            cur_pre->next = cur->next;
            cur = cur->next;
        }
        return cur->val;
    }
};