C# 使用 LinkedList 解決約瑟夫環問題

問題

能否用 C# LinkedList<T> 實現約瑟夫環（Josephus Problem）？

答案：完全可以，且非常適合

LinkedList<T> 提供 O(1) 刪除當前節點、雙向遍歷，完美契合「圓圈中每隔 k 個刪除一個」的場景。

核心代碼

using System;
using System.Collections.Generic;

public class Josephus {
    public static int Solve(int n, int k) {
        var circle = new LinkedList();
        for (int i = 1; i <= n; i++) circle.AddLast(i);
        
        var current = circle.First;
        while (circle.Count > 1) {
            // 移動 k-1 步 (當前節點算第1步)
            for (int i = 1; i < k; i++) {
                current = current.Next ?? circle.First; // 環形
            }
            var toRemove = current;
            current = current.Next ?? circle.First; // 預先移到下一個
            circle.Remove(toRemove);
        }
        return circle.First.Value;
    }
}

// 測試
Console.WriteLine(Josephus.Solve(5, 2)); // 經典 5人報數2 -> 3
Console.WriteLine(Josephus.Solve(41, 3)); // 約瑟夫傳說 41人報數3 -> 31

關鍵點解析

• 環形遍歷：current.Next ?? circle.First 實現尾部回頭。
• 安全刪除：先保存 toRemove，再移動 current 到下一節點，最後 Remove，避免迭代器失效。
• 性能：每輪 O(k)，總 O(nk)。若 k 很大可用數學公式 O(n) 或段式樹 O(n log n) 優化，但鏈表實現最直觀。

擴展：輸出完整淘汰順序

public static List EliminationOrder(int n, int k) {
    var circle = new LinkedList();
    for (int i = 1; i <= n; i++) circle.AddLast(i);
    var order = new List();
    var current = circle.First;
    while (circle.Count > 0) {
        for (int i = 1; i < k; i++)
            current = current.Next ?? circle.First;
        order.Add(current.Value);
        var next = current.Next ?? circle.First;
        circle.Remove(current);
        current = next;
    }
    return order;
}

參考資源

• C# 約瑟夫環多種實現
• MSDN: LinkedList<T> 類文檔