Java 實現約瑟夫環：環形鏈表解決經典數學問題

約瑟夫環是經典的數學應用問題：n 人圍圈，從第 k 人開始報數，數到 m 的人出列，下一人繼續從 1 報數，循環至所有人出列。本文用 Java 環形鏈表優雅實現此算法。

問題形式化

• 輸入：總人數 n、報數上限 m（起始位置簡化為 1）。
• 輸出：出列順序序列。
• 核心：循環刪除鏈表節點。

環形鏈表實現

import java.util.Scanner;

public class Josephus {
    // 節點定義
    private static class Node {
        int no;       // 編號
        Node next;    // 下一節點
        Node(int no) { this.no = no; }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("請輸入總人數：");
        int total = scanner.nextInt();
        System.out.print("請輸入報數大小：");
        int step = scanner.nextInt();

        // 1. 建立環形鏈表
        Node head = new Node(1);
        Node cur = head;
        for (int i = 2; i <= total; i++) {
            cur.next = new Node(i);
            cur = cur.next;
        }
        cur.next = head; // 首尾相連，形成環

        // 2. 模擬出列過程
        System.out.println("以下是出列順序:");
        Node prev = cur; // prev 指向尾節點，cur 指向頭節點
        // 當只剩一個節點時：prev == cur
        while (prev != cur) {
            // 移動 step-1 步，prev 停在待刪除節點的前一個
            for (int i = 1; i < step; i++) {
                prev = prev.next;
            }
            // prev.next 即為出列節點
            System.out.println(prev.next.no);
            // 刪除節點：跳過 prev.next
            prev.next = prev.next.next;
        }
        // 最後剩餘節點
        System.out.println(prev.next.no);
    }
}

算法邏輯圖解

初始環：1 → 2 → 3 → 4 → 5 → (回 1)
step=3

第1輪：prev從5移動2步到2，刪除3 → 輸出3
環：1 → 2 → 4 → 5

第2輪：prev從2移動2步到5，刪除1 → 輸出1
環：2 → 4 → 5

第3輪：prev從5移動2步到4，刪除5 → 輸出5
環：2 → 4

第4輪：prev從4移動2步到2，刪除4 → 輸出4
環：2

最後：輸出2
出列序列：3,1,5,4,2

複雜度分析

• 時間複雜度：O(n × m)。每次出列需移動 m 步，共 n 次。
• 空間複雜度：O(n)。存儲 n 個節點。

若 m 很大，可優化為 step = step % remainingCount（剩餘節點數），避免多餘繞圈。

數學解法補充（O(n) 遞推公式）

遞推公式：f(1) = 0; f(i) = (f(i-1) + m) % i（0 基索引）。最終結果 +1 為 1 基編碼答案。僅能求最後倖存者，無法輸出完整出列序列。

// 僅求最後倖存者編號 (1-based)
public static int josephusMath(int n, int m) {
    int result = 0; // f(1) = 0
    for (int i = 2; i <= n; i++) {
        result = (result + m) % i;
    }
    return result + 1;
}

擴充應用

• 遊戲開發：輪流機制、淘汰賽邏輯。
• 負載均衡：環形輪詢調度。
• 資料結構教學：環形鏈表經典應用案例。