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

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

        // step2 : 在链表内做算法
        int index = 1;
        curr = head;
        cout << curr->val << endl;
        
        while(curr->next != curr) {
            if (++index == m) {
                curr->next = curr->next->next;
                index = 1;
            }
            curr = curr->next;
        }
        // 返回值
        return curr->val;
        // write code here
    }
};