Java 单向循环链表实现约瑟夫问题

思路说明单向循环链表结构节点包含编号、下一个节点引用尾节点指向头节点形成环约瑟夫规则n 个人围成圈从第 1 个人开始报数数到 k 的人出列下一个人重新从 1 报数直到只剩最后一人链表操作核心删除报数到 k 的节点循环遍历环形链表完整代码java运行public class JosephusCircle { // 环形链表节点 static class Node { int num; // 人员编号 Node next; // 下一个节点 public Node(int num) { this.num num; } } /** * 构建单向循环链表 * param personNum 总人数n * return 返回头节点 */ public static Node createCircle(int personNum) { if (personNum 1) { throw new IllegalArgumentException(人数不能小于1); } Node head null; // 头节点 Node cur null; // 辅助指针 for (int i 1; i personNum; i) { Node node new Node(i); // 第一个节点 if (i 1) { head node; cur head; } else { cur.next node; cur cur.next; } } // 尾节点指向头形成循环 cur.next head; return head; } /** * 约瑟夫出圈逻辑 * param n 总人数 * param k 报数上限数到k出圈 */ public static void josephus(int n, int k) { Node head createCircle(n); // pre 指向最后一个节点head前一个方便删除节点 Node pre head; while (pre.next ! head) { pre pre.next; } System.out.println(出圈顺序); // 循环直到只剩一个节点 while (pre ! head) { // 报数k次head走到要出圈的人pre跟在后方 for (int i 1; i k; i) { pre pre.next; head head.next; } // head是要出圈节点 System.out.print(head.num ); // 删除当前head节点 head head.next; pre.next head; } // 最后剩下的人 System.out.println(\n最后存活编号 head.num); } public static void main(String[] args) { // 测试5个人数到3出圈 int total 5; int count 3; josephus(total, count); } }代码解析1. Node 节点类num人的编号1,2,3...nnext指向下一个节点尾节点nexthead构成环2. createCircle 创建环形链表循环创建 n 个节点第一个节点作为头节点遍历结束后尾节点cur.next head闭合循环链表3. josephus 核心出圈逻辑pre 指针始终在head前一位链表删除必须依赖前驱节点每次循环移动k-1次指针head定位到需要出圈的人删除逻辑head head.next; pre.next head断开出圈节点循环终止条件pre head链表只剩最后一个节点运行测试结果输入5 人数 3 出圈plaintext出圈顺序 3 1 5 2 最后存活编号4扩展测试示例示例 110 人数 5 出圈java运行josephus(10,5);示例 21 人边界测试java运行josephus(1,2); // 输出最后存活编号1算法优缺点优点完全模拟真人围成圈报数的过程逻辑直观环形链表操作理解清晰缺点时间复杂度 O (n*k)数据量大时效率低数学公式解法递推公式效率更高但无法体现链表操作补充约瑟夫数学公式对比参考非链表实现java运行// f(n) (f(n-1)k) % n public static int mathJosephus(int n, int k) { int res 0; for (int i 2; i n; i) { res (res k) % i; } return res 1; // 编号从1开始1修正 }