1.4 循环链表实现Joseph环

约瑟夫环问题，是一个经典的循环链表问题，题意是：已知 n 个人（分别用编号 1，2，3，…，n 表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从 1 开始，还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，直到圆桌上剩余一个人。

#include "stdafx.h"

typedef struct node {
    int number;
    struct node* next;
}person;

person * initLink(int n) {
    person *head = (person*)malloc(sizeof(person));
    head->number = 1;
    head->next = NULL;
    person *ring = head;
    for (int i = 2; i <= n; i++) {
        person * body = (person *)malloc(sizeof(person));
        body->number = i;
        body->next = NULL;
        ring->next = body;
        ring = ring->next;
    }
    ring->next = head;
    return head;
}

void findAndKick(person * head, int start, int kick) {
    person *tail = head;
    while (tail->next != head) {
        tail = tail->next;
    }
    person *p = head;
    while (p->number != start) {
        tail = p;
        p = p->next;
    }//p为需要删除的节点， tail为直接前驱
    while (p->next != p) {
        for (int i = 1; i < kick; i++) {
            tail = p;
            p = p->next;
        }
        tail->next = p->next;
        printf("the person with number:  %d is kicked out.\n", p->number);
        free(p);
        p = tail->next;
    }
    printf("the last person to be kicked out is number:  %d.\n", p->number);
    free(p);
}


int main() {
    printf("please enter the total number of persons:  ");
    int n;
    scanf("%d", &n);
    person * head = initLink(n);
    printf("the counting will start from number k( k>=1 and k<=%d):  ", n);
    int start;
    scanf_s("%d", &start);
    printf("the person counting m will be kicked out:  ");
    int kick;
    scanf_s("%d", &kick);

    findAndKick(head, start, kick);
    return 0;
}