1. 什么是约瑟夫环问题约瑟夫环Josephus Problem是一个著名的数学应用题 已知$n$个人以编号$1, 2, 3...n$分别表示围坐在一张圆桌周围。从编号为$k$的人开始报数数到$m$的那个人出列他的下一个人又从$1$开始报数数到$m$的那个人又出列依此规律重复下去直到圆桌周围的人全部出列。2. 解题思路循环链表解决这个问题的核心难点在于“环形”逻辑。使用不带头结点的单向循环链表是最直观、最符合物理模型的解法构建环每个节点的next指向下一个最后一个节点的next指回表头。定位起点先找到第k个开始报数的人。报数与删除移动m-1次找到目标节点将其从链表中删除并释放内存。终止条件当链表中只剩最后一个节点时pq任务完成.3. 代码实现 CC#include iostream using namespace std; // 定义链表节点 struct Node { Node(int data 0) : data_(data), next_(nullptr) {} int data_; Node* next_; }; /** * param head 循环链表首地址 * param k 从第k个人开始报数 * param m 报数到m的人出列 */ void Joseph(Node* head, int k, int m) { if (head nullptr || k 1 || m 1) return; Node* p head; // 报数指针 Node* q head; // 始终指向p的前驱节点方便删除 // 1. q 先指向最后一个节点构建前驱关系 while (q-next_ ! head) { q q-next_; } // 2. 移动到第 k 个人开始报数 for (int i 1; i k; i) { q p; p p-next_; } // 3. 循环报数并出列 cout 出列顺序: ; while (true) { // 报数 m-1 次p指向报数m的人 for (int i 1; i m; i) { q p; p p-next_; } // 打印并出列 cout p-data_ ; // 终止条件如果只剩最后一个节点 if (p q) { delete p; break; } // 删除节点 p并重置 p 指向下一个起始位置 q-next_ p-next_; delete p; p q-next_; } cout endl; } int main() { // 手动构建 1-8 的循环链表 Node* head new Node(1); Node* n2 new Node(2); Node* n3 new Node(3); Node* n4 new Node(4); Node* n5 new Node(5); Node* n6 new Node(6); Node* n7 new Node(7); Node* n8 new Node(8); head-next_ n2; n2-next_ n3; n3-next_ n4; n4-next_ n5; n5-next_ n6; n6-next_ n7; n7-next_ n8; n8-next_ head; // 测试从第1个人开始报到3的人出列 Joseph(head, 1, 3); return 0; }4. 关键点深度解析为什么需要两个指针 和 pq在单向链表中要删除节点 我们必须知道它的前驱节点 。通过 我们才能在逻辑上跳过 进而安全地 。q-next_ p-next_delete p复杂度分析时间复杂度O(n *m)。我们需要出列n次每次报数m个。空间复杂度O(n)。用于存储n个节点的链表。细节提醒在 函数中我们处理了 的情况。这是循环链表唯一的退出条件意味着圈子里只剩下最后一个人了此时释放内存并退出循环。Josephp q5. 总结约瑟夫环是理解链表操作尤其是指针重定向和内存管理的绝佳案例。虽然对于超大规模的数据我们可以使用数学递推公式在$O(n)$时间内直接算出胜出者但链表法能更直观地还原问题的动态过程。
【经典算法】手把手带你实现约瑟夫环（C++ 循环链表版）
1. 什么是约瑟夫环问题约瑟夫环Josephus Problem是一个著名的数学应用题 已知$n$个人以编号$1, 2, 3...n$分别表示围坐在一张圆桌周围。从编号为$k$的人开始报数数到$m$的那个人出列他的下一个人又从$1$开始报数数到$m$的那个人又出列依此规律重复下去直到圆桌周围的人全部出列。2. 解题思路循环链表解决这个问题的核心难点在于“环形”逻辑。使用不带头结点的单向循环链表是最直观、最符合物理模型的解法构建环每个节点的next指向下一个最后一个节点的next指回表头。定位起点先找到第k个开始报数的人。报数与删除移动m-1次找到目标节点将其从链表中删除并释放内存。终止条件当链表中只剩最后一个节点时pq任务完成.3. 代码实现 CC#include iostream using namespace std; // 定义链表节点 struct Node { Node(int data 0) : data_(data), next_(nullptr) {} int data_; Node* next_; }; /** * param head 循环链表首地址 * param k 从第k个人开始报数 * param m 报数到m的人出列 */ void Joseph(Node* head, int k, int m) { if (head nullptr || k 1 || m 1) return; Node* p head; // 报数指针 Node* q head; // 始终指向p的前驱节点方便删除 // 1. q 先指向最后一个节点构建前驱关系 while (q-next_ ! head) { q q-next_; } // 2. 移动到第 k 个人开始报数 for (int i 1; i k; i) { q p; p p-next_; } // 3. 循环报数并出列 cout 出列顺序: ; while (true) { // 报数 m-1 次p指向报数m的人 for (int i 1; i m; i) { q p; p p-next_; } // 打印并出列 cout p-data_ ; // 终止条件如果只剩最后一个节点 if (p q) { delete p; break; } // 删除节点 p并重置 p 指向下一个起始位置 q-next_ p-next_; delete p; p q-next_; } cout endl; } int main() { // 手动构建 1-8 的循环链表 Node* head new Node(1); Node* n2 new Node(2); Node* n3 new Node(3); Node* n4 new Node(4); Node* n5 new Node(5); Node* n6 new Node(6); Node* n7 new Node(7); Node* n8 new Node(8); head-next_ n2; n2-next_ n3; n3-next_ n4; n4-next_ n5; n5-next_ n6; n6-next_ n7; n7-next_ n8; n8-next_ head; // 测试从第1个人开始报到3的人出列 Joseph(head, 1, 3); return 0; }4. 关键点深度解析为什么需要两个指针 和 pq在单向链表中要删除节点 我们必须知道它的前驱节点 。通过 我们才能在逻辑上跳过 进而安全地 。q-next_ p-next_delete p复杂度分析时间复杂度O(n *m)。我们需要出列n次每次报数m个。空间复杂度O(n)。用于存储n个节点的链表。细节提醒在 函数中我们处理了 的情况。这是循环链表唯一的退出条件意味着圈子里只剩下最后一个人了此时释放内存并退出循环。Josephp q5. 总结约瑟夫环是理解链表操作尤其是指针重定向和内存管理的绝佳案例。虽然对于超大规模的数据我们可以使用数学递推公式在$O(n)$时间内直接算出胜出者但链表法能更直观地还原问题的动态过程。
