約瑟夫問題 C 語言完整實作：循環鏈表解法詳解

問題描述

n 人圍成一圈，從第 m 人開始報數，每數到 s 就將該人移出圈外，下一人繼續從 1 開始報數，直至所有人移出。輸出移出順序。

資料結構：循環單向鏈表

typedef struct Node {
    int data;
    struct Node* next;
} Node;
typedef Node* LinkList;

建立約瑟夫環

void CreateJosephLoop(LinkList* L, int number) {
    *L = malloc(sizeof(Node));
    (*L)->data = 1;
    (*L)->next = *L;                 /* 自環，形成單節點環 */

    LinkList tail = *L;
    for (int i = 1; i < number; i++) {
        LinkList new = malloc(sizeof(Node));
        new->data = i + 1;
        new->next = tail->next;      /* 插入尾部，維持環狀 */
        tail->next = new;
        tail = new;
    }
}

核心解題流程

void JosephProblem(int loopSize, int from, int stepBy) {
    LinkList L;
    CreateJosephLoop(&L, loopSize);

    /* 移動到起始位置 */
    int seekStart = 1;
    while (seekStart < from) {
        L = L->next;
        seekStart++;
    }

    /* 開始淘汰 */
    while (L->data != L->next->data) {      /* 還有超過 1 人 */
        for (int i = 1; i < stepBy - 1; i++) /* 走 stepBy-1 步 */
            L = L->next;

        LinkList temp = L->next;            /* 要刪除的節點 */
        printf("%d-->", temp->data);
        L->next = L->next->next;            /* 從環中摘除 */
        L = L->next;                        /* 下一輪從下一人開始 */
        free(temp);
    }
    printf("%d\n", L->data);                /* 最後一人 */
}

測試主程式

int main() {
    JosephProblem(10, 3, 4);   /* 10 人，從 3 開始，報 4 出局 */
    JosephProblem(41, 1, 3);   /* 經典 41 人、報 3 */
    return 0;
}

執行結果

複雜度分析

數學優化方向（O(n) 或 O(n log n)）

• 遞歸公式：`f(1) = 0; f(i) = (f(i-1) + s) % i` 可直接算出最後倖存者位置，但無法輸出完整淘汰順序。
• 段式樹 / 核狀樹：維護「剩餘人數」前綴和，單次查找第 k 人可達 O(log n)，整體 O(n log n)。
• 順序表模擬：用陣列 + 邏輯刪除（標記法），配合模運算跳躍，常數項較小，工程上常用。

鏈表解法雖非最優，但直觀展示了「環狀結構 + 指標操作」的核心思想，是資料結構教學與面試經典必考題。