Josephus 問題高效解法：模運算優化與雙向鏈表實作

問題定義

N 人圍圈編號 1∼N，從 1 開始報數，報到 M 者出列，剩餘繼續從 1 報數，直至全數出列。輸出出列順序。

兩大優化策略

1. 模運算縮減步數：當 M > N 時，實際步數 M' = M % N（若餘 0 則為 N）。避免重複繞圈。
2. 雙向鏈表就近移動：若 M' > N/2，反向移動 N - M' + 1 步更快。需雙向鏈表支援 Prev 操作。

範例推演：N=5, M=9

出列序列：4, 5, 3, 1, 2

C 完整實作（含雙向循環鏈表 ADT）

// dlinkedlist.h
typedef int ElementType;
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List, Position;
List CreateList(ElementType X);
void Insert(ElementType X, List L, Position P);
void Remove(Position P, List *L);
Position NextPosition(Position P);
Position PreviousPosition(Position P);
ElementType Retrieve(Position P);

// josephus.c
#define N 5
#define M 9
static List init();
void process(List l);

int main() {
    List josephus = init();
    process(josephus);
    return 0;
}

void process(List l) {
    int n = N, m = M % n;
    Position p = l;
    while (n > 1) {
        if (m > n/2) {
            for (int i = 0; i < n - m + 1; ++i) p = PreviousPosition(p);
        } else {
            for (int i = 0; i < m; ++i) p = NextPosition(p);
        }
        p = PreviousPosition(p);  // 定位待刪除節點前驅
        printf("%d out\n", Retrieve(NextPosition(p)));
        Remove(NextPosition(p), &l);
        --n; m = M % n;
        printf("current: "); print(l);
    }
}

// 關鍵 Remove 實作：雙指標修正頭尾連接
void Remove(Position P, List *L) {
    if (P == *L) {
        if ((*L)->Next == *L) { free(*L); *L = NULL; return; }
        *L = (*L)->Next;  // 更新頭指標
    }
    P->Prev->Next = P->Next;
    P->Next->Prev = P->Prev;
    free(P);
}

關鍵點：傳遞 List* (指標的指標)

刪除頭節點時需修改呼叫端的 List 變數值（即頭指標地址），故參數為 List*。同理：修改 int 傳 int*，修改 int* 傳 int**。

複雜度分析

• 時間：O(N * min(M, N))，優化後實際步數大幅減少。
• 空間：O(N) 鏈表節點。