約瑟夫問題經典算法，環形連結清單的運用

問題背景：

據說在很久很久以前，約瑟夫及其部下被逼退到了一個山洞裡面，走頭無路，大家又不甘投降叛變，于是大家決定一起赴死，他們一起圍成了一個圈，然後準備依次報數，當誰的數字為3的時候就自殺，後面的人從1開始依次報數，遇到3又自殺，如此循環往複，問最後一個自殺的人是誰？例如如下序列：

算法分析

#include <stdio.h>
#include <stdlib.h>

//聲明結構體
typedef struct node *Link;

//定義結構體
struct node {
    int number;
    Link next;
};

//輸出測試資料
void print_data(Link head, int totalNum){
    int i;
    Link temp = head;
    for(i = 1; i <= totalNum; i++){
        printf("%d ", temp->number);
        temp = temp->next;
    }
}

int main(void) {
    int totalNum = 10;//總共的人數
    int space = 3;//間隔數
    Link head = malloc(sizeof *head);
    Link x = head;
    //将頭節點指向自身
    head->number = 1;
    head->next = head;
    
    //開始進行生成一個環形連結清單
    for(int i = 2 ; i <= totalNum; i++){
        x->next = malloc(sizeof *x);
        x->next->next = head;
        x->next->number = i;
        x = x->next;
    }
    
    //列印測試
    printf("隊列原始順序:\n");
    print_data(head, totalNum);
    
    x = head;
    //依次将環形連結清單中的某個位置的值去掉
    printf("\n死亡士兵的順序:\n");
    while(x != x->next){
        for(int i = 2; i < space; i++){
            x = x->next;
        }
        printf("%d ", x->next->number);
        x->next = x->next->next;
        x = x->next;
    }
    printf("\n最後自殺的士兵:\n");
    printf("%d ", x->number);
    return 0;
}