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