构建一个循环链表,然后不断计数就好了,但是要注意,因为是循环链表,删除到只剩最后一个结点的时候就可以停止计数了,因为他肯定是最后一个出圈的。记得这道题是大一学到链表的时候做的题目。

#include<iostream>

using namespace std;

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int v) : val(v), next(NULL){}
};
// 初始化循环链表
ListNode* init(int n){
    ListNode* head = new ListNode(1), *h = head;
    for(int i = 2; i <= n; i ++){
        h->next = new ListNode(i);
        h = h->next;
    }
    h->next = head;
    return head;
}

void count(ListNode* head){
    int cnt = 2;
    ListNode* pre = head;
    head = head->next;
    // 遍历循环链表直到只剩下一个结点
    while(head->next != head){
        if(cnt == 3){
            pre->next = head->next;
            // 从 1 开始重新计数
            cnt = 1;
            cout << head->val << " ";
            // 删除结点
            head->next = NULL;
            free(head);
        } else {
            pre = head; cnt ++;
        }
        head = pre->next;
    }
    cout << head->val << endl;
}

int main(){
    int m, n;
    cin >> m;
    for(int i = 0; i < m; i ++){
        cin >> n;
        ListNode* head = init(n);
        count(head);
    }
    return 0;
}