Java 環形鏈表解決約瑟夫斯問題完整實現

問題描述

有 n 個人圍成一圈，編號 1~n。從第 s 人開始報數，數到 d 的人出列，下一人繼續從 1 報數，循環直到所有人出列。要求使用單向環形鏈表實現。

數據結構設計

public class LinkNode {
    public int data;       // 節點值（編號）
    public LinkNode next;  // 指向下一節點

    public LinkNode(int k) {
        data = k;
        next = null;
    }
}

核心邏輯：Josephus 類

import java.util.Scanner;

class Josephus {
    public static void printJosephus(int n, int s, int d) {
        // 1. 構建長度為 n 的環形鏈表
        LinkNode head = new LinkNode(1);
        head.next = head; // 首尾相連
        LinkNode tail = head;

        for (int i = 2; i <= n; i++) {
            LinkNode q = new LinkNode(i);
            q.next = head;   // 新節點指向頭
            tail.next = q;   // 原尾節點指向新節點
            tail = q;        // 更新尾指針
        }

        // 2. 移動到起始報數位置 (s-1 步)
        LinkNode p = head;
        for (int j = 1; j < s; j++) {
            p = p.next;
        }

        // 3. 循環出列
        while (p.next != p) { // 當前節點不指向自己（還有不止一個節點）
            // 報數 d-1 步，p 停在「被刪除節點的前一個」
            for (int j = 1; j < d; j++) {
                p = p.next;
            }
            System.out.print(p.next.data + " "); // 輸出出列者編號
            p.next = p.next.next; // 從環中移除
            p = p.next;           // 下一輪從被刪除節點的下一個開始
        }
        System.out.print(p.data); // 最後一人
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); // 總人數
        int s = in.nextInt(); // 起始位置
        int d = in.nextInt(); // 報數上限
        printJosephus(n, s, d);
    }
}

代碼走讀示例

輸入：5 1 2（5 人，從 1 開始，數 2 出列）

1. 初始環：1→2→3→4→5→1
2. p 指向 1（s=1 不移動）
3. 第一輪：p 移動 1 步到 1，刪除 p.next=2 → 輸出 2，環變 1→3→4→5→1，p 指向 3
4. 第二輪：p 移動 1 步到 3，刪除 4 → 輸出 4，環 1→3→5→1，p 指向 5
5. 第三輪：p 移動 1 步到 5，刪除 1 → 輸出 1，環 3→5→3，p 指向 3
6. 第四輪：p 移動 1 步到 3，刪除 5 → 輸出 5，環 3→3，p 指向 3
7. 循環結束，輸出最後 3

最終輸出：2 4 1 5 3

複雜度分析

• 時間：O(n × d) — 每次出列需走 d 步，共 n 次。
• 空間：O(n) — 存儲 n 個節點。

優化方向

若 d 很大，可用 d %= 當前剩餘人數 減少無效循環；或引入順序統計樹（如線段樹、Treap）實現 O(n log n) 解法，但環形鏈表最直觀易懂，適合教學與面試。