C# 鏈表完整實作：單向、循環、約瑟夫斯問題——從基礎節點操作到經典算法應用

前言：為什麼還要手寫鏈表？

.NET 內建 LinkedList 已高度優化，但在面試、教學、特定效能場景（如自訂記憶體池、內核級開發、嵌入式無 GC 環境）理解鏈表底層機制至關重要。本文提供單向鏈表、循環鏈表完整實作，並以經典「約瑟夫斯問題」展示循環鏈表實戰應用。

一、單向鏈表（Single Linked List）

節點定義

public class Node {
    public T Item { get; set; }
    public Node Next { get; set; }

    public Node(T item, Node next = null) {
        Item = item;
        Next = next;
    }
}

鏈表核心操作封裝

public class SinglyLinkedList {
    private Node _head; // 虛擬頭節點
    private int _count;

    public SinglyLinkedList() {
        _head = new Node(default); // 虛擬頭節點簡化邊界條件
        _count = 0;
    }

    public int Count => _count;

    // 尾部插入 O(1) 若維護尾指針，此處為教學簡單 O(N)
    public void AddLast(T item) {
        Node cur = _head;
        while (cur.Next != null) cur = cur.Next;
        cur.Next = new Node(item);
        _count++;
    }

    // 指定位置插入 (0-based, 0=頭部)
    public bool Insert(int index, T item) {
        if (index < 0 || index > _count) return false;
        Node cur = _head;
        for (int i = 0; i < index; i++) cur = cur.Next;
        cur.Next = new Node(item, cur.Next);
        _count++;
        return true;
    }

    // 刪除最後一個
    public bool RemoveLast() {
        if (_count == 0) return false;
        Node cur = _head;
        while (cur.Next.Next != null) cur = cur.Next;
        cur.Next = null;
        _count--;
        return true;
    }

    // 指定位置刪除
    public bool RemoveAt(int index) {
        if (index < 0 || index >= _count) return false;
        Node cur = _head;
        for (int i = 0; i < index; i++) cur = cur.Next;
        cur.Next = cur.Next.Next;
        _count--;
        return true;
    }

    // 按值刪除首個匹配項
    public bool Remove(T item) {
        Node cur = _head;
        while (cur.Next != null) {
            if (EqualityComparer.Default.Equals(cur.Next.Item, item)) {
                cur.Next = cur.Next.Next;
                _count--;
                return true;
            }
            cur = cur.Next;
        }
        return false;
    }

    // 獲取指定位置節點值
    public T Get(int index) {
        if (index < 0 || index >= _count) throw new ArgumentOutOfRangeException();
        Node cur = _head.Next;
        for (int i = 0; i < index; i++) cur = cur.Next;
        return cur.Item;
    }

    // 反轉鏈表（迭代法）
    public void Reverse() {
        Node prev = null, cur = _head.Next;
        while (cur != null) {
            Node next = cur.Next;
            cur.Next = prev;
            prev = cur;
            cur = next;
        }
        _head.Next = prev;
    }

    // 排序（氣泡排序教學用，實務建議轉 List 排序後重建）
    public void Sort(Comparison cmp = null) {
        cmp ??= Comparer.Default.Compare;
        for (int i = 0; i < _count - 1; i++) {
            for (int j = 0; j < _count - 1 - i; j++) {
                if (cmp(Get(j), Get(j + 1)) > 0) {
                    // 交換節點值（簡化版，實際應交換節點指針）
                    T tmp = Get(j);
                    Set(j, Get(j + 1));
                    Set(j + 1, tmp);
                }
            }
        }
    }

    private void Set(int index, T value) {
        Node cur = _head.Next;
        for (int i = 0; i < index; i++) cur = cur.Next;
        cur.Item = value;
    }

    // 遍歷輸出
    public IEnumerable AsEnumerable() {
        Node cur = _head.Next;
        while (cur != null) {
            yield return cur.Item;
            cur = cur.Next;
        }
    }
}

二、循環鏈表（Circular Linked List）

特徵：尾節點 Next 指向頭節點，形成環。適用於循環輪詢、資源池、約瑟夫斯問題。

極簡實作

public class CircularList {
    public class Node {
        public T Value;
        public Node Next;
        public Node(T val) { Value = val; }
    }

    private Node _current; // 當前指標

    // 插入節點於 current 之後，並返回新節點
    public Node Insert(Node current, T value) {
        Node node = new Node(value);
        if (current == null) {
            node.Next = node; // 首節點指向自己
            return node;
        }
        node.Next = current.Next;
        current.Next = node;
        return node;
    }

    // 移除 current 之後的節點
    public void Remove(Node current) {
        if (current == null || current.Next == current) return; // 空或單節點
        current.Next = current.Next.Next;
    }

    // 獲取下一節點
    public Node Next(Node current) => current?.Next;
    public T Value(Node current) => current?.Value;
}

三、經典應用：約瑟夫斯問題

問題：N 人圍圈，從第 1 人開始報數，數到 M 的人出列，下一人繼續從 1 報數，求最後倖存者位置。

循環鏈表模擬解法（直觀、易懂）

public class Josephus {
    /// 
模擬法：O(N*M) 時間，O(N) 空間
    public static T SolveBySimulation(T[] items, int m) {
        if (items == null || items.Length == 0) throw new ArgumentException();
        if (m <= 0) throw new ArgumentException("M 必須 > 0");

        var list = new CircularList();
        CircularList.Node current = null;

        // 建立循環鏈表
        foreach (var item in items) {
            current = list.Insert(current, item);
        }

        // 模擬淘汰過程
        while (current != list.Next(current)) { // 直到剩最後一個
            for (int i = 1; i < m; i++) // 移動 M-1 步
                current = list.Next(current);
            list.Remove(current); // 移除下一個（即第 M 個）
            current = list.Next(current); // 從下一個繼續
        }
        return list.Value(current);
    }

    /// 
數學遞推法：O(N) 時間，O(1) 空間（最優解）
    /// 0-based 索引
    public static int SolveByMath(int n, int m) {
        int result = 0; // f(1,m) = 0
        for (int i = 2; i <= n; i++) {
            result = (result + m) % i; // f(i,m) = (f(i-1,m) + m) % i
        }
        return result; // 轉 1-based: result + 1
    }
}

測試驗證

var names = new[] { "A", "B", "C", "D", "E" };
int m = 3;

Console.WriteLine($"模擬法倖存者: {Josephus.SolveBySimulation(names, m)}"); // C
Console.WriteLine($"數學法索引(0-based): {Josephus.SolveByMath(5, 3)}");     // 3 (即第 4 人，對應 names[3]="D"? 待核對)
// 注意：數學法回傳 0-based 索引，需對應原始陣列
// 經典 Josephus(5,3) 淘汰順序: 3(C) -> 1(A) -> 5(E) -> 2(B) -> 倖存 4(D)
// 數學法 f(5,3)=3 即 names[3]="D" 正確

四、進階主題與避坑指南

總結

掌握 虛擬頭節點單向鏈表 的增刪改查、循環鏈表 的自環與指針操作，並能靈活選擇 模擬法（教學/驗證）與 數學遞推法（生產/大數據）解決約瑟夫斯問題，即可應付絕大多數鏈表相關面試與工程場景。記住：實務中優先用標準庫，手寫僅為理解本質與特殊約束環境。