题解 | #围圈报数#

#include<bits/stdc++.h>
using namespace std;
// N 个人围成一圈顺序编号，从1 号开始按1、2、3 顺序报数，报3者退出圈外，其余的人再从1、2、3 开始报数，报3 的人再退出圈外，依次类推。
// 请按退出顺序输出每个退出人的原序号。要求使用环行链表编程。
struct Node {
	int num;
	Node *next;
};

void quit(Node* &pre) {
	if (pre->next == pre) {
		printf("%d ", pre->num);
		return;
	}
	Node *t = pre->next;
	pre->next = t->next;
	printf("%d ", t->num);
	delete t;
	return;
}

int main() {
	int n, m;
	cin >> m;
	for (int j = 0; j < m; j++) {
		cin >> n;
		Node *head = new Node;
		head->num = 1;
		Node *tmp = head;
		for (int i = 2; i <= n; i++) {
			tmp->next = new Node;
			tmp = tmp->next;
			tmp->num = i;
		}
		tmp->next = head;
		while (tmp->next != tmp) {
			for (int i = 0; i < 2; i++) {
				tmp = tmp->next;
			}
			quit(tmp);
		}
		printf("%d\n", tmp->num);
	}
}