1. 约瑟夫问题

题目（要求用循环链表实现）

约瑟夫问题是一个经典的问题。已知n个人（不妨分别以编号1，2，3，…，n 代表 ）围坐在一张圆桌周围，从编号为 k 的人开始，从1开始顺时针报数1, 2, 3, ...，顺时针数到m 的那个人，出列并输出。然后从出列的下一个人开始，从1开始继续顺时针报数，数到m的那个人，出列并输出，…依此重复下去，直到圆桌周围的人全部出列。

输入：n, k, m

输出：按照出列的顺序依次输出出列人的编号，编号中间相隔一个空格,每10个编号为一行。

非法输入的对应输出如下

a)

输入：：n、k、m任一个小于1
输出：n,m,k must bigger than 0.

b)

输入：k>n

输出：k should not bigger than n.

例:

输入：9,3,2

输出：4 6 8 1 3 7 2 9 5

---

注意事项

1. 创建循环链表时，需要将链表的首尾相连，形成循环。
2. 在每次出列后，要及时释放被删除节点的内存空间，避免内存泄漏问题。
3. 在输出结果时，需要根据出列人数的情况进行换行和空格的处理，确保输出结果符合题目要求。
    

---

C++完整代码(含注释）

#include 
#include 
#include 
using namespace std;
 
struct ListNode {
	int val;
	ListNode* next;
	ListNode(int x) : val(x), next(NULL) {}
};
 
int main() {
	int n, k, m;
	scanf("%d%*c%d%*c%d", &n, &k, &m);
 
	// 检查输入的合法性
	if (n < 1 || k < 1 || m < 1) {
		cout << "n,m,k must bigger than 0." << endl;
		return 0;
	}
	if (k > n) {
		cout << "k should not bigger than n." << endl;
		return 0;
	}
 
	// 创建循环链表
	ListNode* head = new ListNode(1); // 创建链表的头节点
	ListNode* cur = head; // 当前节点指针
	for (int i = 2; i <= n; i++) { // 创建链表的其他节点
		cur->next = new ListNode(i);
		cur = cur->next;
	}
	cur->next = head; // 将链表首尾相连，形成循环链表
 
	// 将cur指针移动到编号为k的节点
	for (int i = 0; i < k - 1; i++) {
		head = head->next;
	}
 
	int count = 0; // 记录出列的人数
	// 开始报数并出列
	while (n) { // 当还有人没有出列时
		if (m > 1) { // 数到m的前一个节点
			for (int i = 0; i < m - 2; i++) {
				head = head->next;
			}
			// 出列并记录编号
			ListNode* temp = head->next;
			cout << temp->val; // 输出出列人的编号
			head->next = temp->next; // 删除出列的节点
			head = head->next; // 移动cur指针到下一个节点
			delete temp; // 释放被删除节点的内存空间
			n--; // 更新剩余人数
			count++; // 更新出列人数
		}
		else { // m等于1时，直接将cur指针指向下一个节点
			cout << head->val; // 输出出列人的编号
			head = head->next; // 移动cur指针到下一个节点
			n--; // 更新剩余人数
		}
 
		// 根据出列人数的情况输出结果
		if (n == 0 && count % 10 != 0) {
			cout << endl; // 所有人都出列且最后一行不满10个编号，换行
		}
		else if (count % 10 == 0) {
			cout << endl; // 出列人数达到10的倍数，换行
		}
		else {
			cout << " "; // 输出编号之间的空格
		}
	}
 
	return 0;
}