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...n）next：指向下一个节点，尾节点next=head构成环
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扩展测试示例
示例 1：10 人，数 5 出圈
java
运行
josephus(10,5);示例 2：1 人边界测试
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修正 }