約瑟夫環問題：循環鏈表C語言實現全流程詳解

問題背景

「約瑟夫環」是經典的圍圈報數問題：n 個人圍成一圈，從 1 開始報數，報到 3 的人退出，剩餘繼續報數，直至剩最後一人。本文展示如何用單向循環鏈表在 C 語言中完整實現此過程，並分析初學者常見的指針未初始化導致運行失敗的坑。

數據結構設計

struct LNODE {
    int data;              // 編號 1~n
    struct LNODE *next;    // 指向下一節點
};
typedef struct LNODE Lnode;
typedef struct LNODE *LinkList;

核心函數實現

1. 建立循環鏈表

struct LNODE *create(int s[]) {
    struct LNODE *head = NULL, *p = NULL, *last = NULL;
    int i = 0;

    head = (struct LNODE *)malloc(sizeof(struct LNODE));
    if (!head) { printf("記憶體分配失敗!"); return NULL; }

    if (s[0] != 0) {
        head->data = s[0];
        head->next = head;   // 首節點自環
        last = head;
        i++;
        while (s[i] != 0) {  // 以 0 為結束標記
            p = (struct LNODE *)malloc(sizeof(struct LNODE));
            last->next = p;
            p->data = s[i];
            p->next = head;  // 新節點指向頭，形成環
            last = p;
            i++;
        }
    }
    return head;
}

2. 列印鏈表（驗證用）

void printlist(struct LNODE *head) {
    struct LNODE *q;
    printf("鏈表內容：\n");
    if (!head) { printf("NULL\n"); return; }
    q = head;
    do {
        printf("%d\t", q->data);
        q = q->next;
    } while (q != head);
    printf("\n");
}

3. 主邏輯：模擬報數與刪除

int main() {
    int circlelist[100], n, i, k = 1;
    printf("請輸入人數：");
    scanf("%d", &n);
    getchar();

    for (i = 0; i < n; i++) circlelist[i] = i + 1; // 編號 1~n
    circlelist[i] = 0;                              // 結束標記

    LinkList p = NULL, q = NULL;
    p = create(circlelist);
    printlist(p);                                   // 列印初始編號

    // 關鍵：指針必須初始化為 NULL，否則野指針導致未定義行為
    while (p->data != p->next->data) {              // 直到剩唯一節點
        if (k != 3) {                               // 未報到 3
            k++;
            q = p;                                  // q 保留前驅
            p = p->next;
        } else {                                    // 報到 3，刪除節點 p
            k = 1;
            printf("%d\t", p->data);                // 輸出退出順序
            q->next = p->next;                      // 斷鏈
            p = q->next;                            // p 移至下一節點
        }
    }
    printf("\n倖存者：%d\n", p->data);
    return 0;
}

避坑指南：指針初始化的重要性

作者在開發時發現：LinkList p, q; 未顯式賦值 NULL 時，編譯無錯誤但程序無法正常執行（可能段錯誤或死循環）。原因在於未初始化的指針持有隨機地址（野指針），首次進入循環時 q = p 或 p = p->next 會導致不可預期行為。

最佳實踐：

1. 定義指針時立即賦值 NULL：LinkList p = NULL, q = NULL;
2. 解引用前檢查非空：if (p) { ... }
3. 釋放後置空：free(p); p = NULL;

複雜度分析

• 時間複雜度：O(n × m)，n 為人數，m 為報數間隔（此處固定 3），實際為 O(n²) 級別。
• 空間複雜度：O(n)，需存儲 n 個節點。

循環鏈表直觀地模擬了「環狀結構與動態刪除」，是理解指釖操作與經典算法的絕佳案例。