【牛客网刷题（数据结构）】：环形链表的约瑟夫问题

描述
编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。
下一个人继续从 1 开始报数。
n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？
O(n)
示例1
好环形链表的约瑟夫问题是一个经典的问题，它的描述如下：有n个人围成一圈，从第一个人开始报数，报到m的人出圈，剩下的人继续从1开始报数，直到剩下最后一个人。现在给定n和m，求最后剩下的人的编号
这个问题可以使用环形链表来解决。具体来说，我们可以先构建一个包含n个节点的环形链表，然后从第一个节点开始遍历链表，每次遍历m个节点，将第m个节点从链表中删除。重复这个过程直到链表中只剩下一个节点为止，这个节点就是最后剩下的节点
输入：
5,2
返回值：
3
说明：
开始5个人 1，2，3，4，5 ，从1开始报数，1->1，2->2编号为2的人离开
1，3，4，5，从3开始报数，3->1，4->2编号为4的人离开
1，3，5，从5开始报数，5->1，1->2编号为1的人离开
3，5，从3开始报数，3->1，5->2编号为5的人离开
最后留下人的编号是3
示例2
输入：
1,1
复制
返回值：
1
关于环形链表的约瑟夫问题，具体思路如下：
首先创建一个环形链表，链表中每个节点代表一个人，节点编号从1开始递增。
然后从第一个节点开始报数，每报到第m个人就将该节点从链表中删除。
删除节点后，从下一个节点重新开始报数，重复上述步骤，直到只剩下一个节点为止。
下面是C++代码实现：

#include <iostream>
using namespace std;struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(NULL) {}
};int josephus(int n, int m) {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; // 将链表首尾相连while (cur->next != cur) { // 只剩下一个节点时结束循环for (int i = 1; i < m; i++) {cur = cur->next;}ListNode* tmp = cur->next;cur->next = tmp->next;delete tmp;}int ans = cur->val;delete cur;return ans;
}int main() {int n, m;cin >> n >> m;cout << josephus(n, m) << endl;return 0;
}

C语言代码实现

#include <stdio.h>
#include <stdlib.h>// 定义链表节点结构体
typedef struct Node {int num;            // 节点编号struct Node *next;  // 指向下一个节点的指针
} Node;// 创建环形链表
Node *createList(int n) {Node *head = NULL, *tail = NULL;for (int i = 1; i <= n; i++) {Node *p = (Node *)malloc(sizeof(Node));p->num = i;if (head == NULL) {head = p;} else {tail->next = p;}tail = p;}tail->next = head;  // 将尾节点指向头节点，形成环形链表return head;
}// 约瑟夫问题求解
void josephus(Node *head, int m) {Node *p = head, *prev = NULL;while (p->next != p) {  // 只剩下一个节点时结束循环for (int i = 1; i < m; i++) {prev = p;p = p->next;}prev->next = p->next;  // 删除节点printf("%d ", p->num);free(p);p = prev->next;  // 从下一个节点重新开始报数}printf("%d\n", p->num);free(p);
}int main() {int n, m;printf("请输入总人数n和报数m：");scanf("%d%d", &n, &m);Node *head = createList(n);josephus(head, m);return 0;
}