C++ 單向循環鏈表實作約瑟夫環問題完整解析

約瑟夫環是經典的演算法問題：m 個小孩圍成一圈，從第一個開始報數，數到 n 的小孩出列，剩餘小孩繼續報數，最終求出最後留下的小孩編號。本文提供基於 C++ 單向循環鏈表的完整實作，並詳細解析關鍵邏輯。

問題建模

• 使用單向循環鏈表自然模擬「圍成一圈」的結構。
• 每個節點儲存小孩編號 s 與指向下一節點的指標 next。
• 刪除節點時只需調整前驅節點的 next 指標，並釋放記憶體。

核心程式碼實作

#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;

class ys {  // 節點類別
    int s;
public:
    ys *next;
    friend ys *set(int n);
    void get(ys *s);
    void putout(ys *t, int m, int n);
};

// 建立含 n 節點的循環鏈表，回傳尾節點指標
ys *set(int n) {
    ys *q = new ys, *h = q;
    for (int i = 1; i < n; ++i) {
        q->s = i;
        q->next = new ys;
        q = q->next;
    }
    q->next = h;  // 首尾相連
    q->s = n;
    return q;  // 回傳尾節點，便於從頭節點開始遍歷
}

// 輸出所有小孩編號（除頭節點外）
void ys::get(ys *s) {
    int tem = s->s;
    while (s->next->s != tem) {
        cout << s->next->s << '\t';
        s = s->next;
    }
}

// 核心邏輯：每 m 步刪除一節點，直到剩最後一個
void ys::putout(ys *t, int m, int n) {
    ys *h = t->next, *p = t;  // h 為當前檢查節點，p 為其前驅
    int i = 0;
    for (; n > 1; ) {
        ++i;
        if (i % m != 0) {
            p = h;
            h = h->next;
        } else {
            p->next = h->next;  // 從鏈表移除 h
            delete h;
            h = p->next;        // 移至下一節點繼續
            --n;
        }
    }
    cout << endl << "n: " << h->s << endl;
}

int main() {
    cout << "請輸入 n 個小孩，間隔為 m：\n";
    int n, m;
    cin >> n >> m;
    ys yue;
    ys *head = set(n);
    yue.get(head);
    yue.putout(head, m, n);
    return 0;
}

關鍵點解析

1. 鏈表建立：set() 回傳尾節點，因尾節點的 next 指向頭節點，方便後續從頭開始遍歷。
2. 報數與刪除：變數 i 累計報數，i % m == 0 時觸發刪除。刪除操作包含：前驅 p 跨過 h、釋放 h 記憶體、h 移至下一節點、剩餘人數 n--。
3. 記憶體管理：每次刪除均呼叫 delete，避免記憶體洩漏。

複雜度分析

• 時間複雜度：O(n × m) —— 最壞情況每輪需遍歷 m 步。
• 空間複雜度：O(n) —— 儲存 n 個節點。

延伸思考

若 n 極大（如 10⁷），鏈表頻繁動態配置記憶體效率較低。可改用數組模擬循環鏈表（next[i] 儲存下一索引），或推導數學遞推公式 f(1)=0; f(i)=(f(i-1)+m)%i 達到 O(n) 時間、O(1) 空間的最優解。