围圈报数

循环链表

#include<stdio.h>
#include <stdlib.h>
int N;
typedef struct Node{
    int id;
    struct Node * next;
}People;
People *init()
{
    People *h = (People *)malloc(sizeof(People)); // 头结点
    h->id = 1;
    h->next = NULL;
    People *p =h;
    for(int i = 2;i<N;i++)
    {
        People *temp = (People *)malloc(sizeof(People));
        temp -> id = i;
        temp -> next = NULL;
        p->next = temp;
        p = p->next;
    }
    People *temp = (People *)malloc(sizeof(People));
    temp -> id = N;
    temp -> next = h;
    p ->next = temp;
    return h;
}
void function(People *head)
{
    People *p = head; // p为出圈后的第一个报数的人
    while(p->next != p) // 至少还有两人
    {
        int num;
        People *delete = p->next->next; // 待出圈的人
        People *q = p->next; // 出圈的人的上一位
        num = delete->id;
        printf("%d ",num);
        q->next = delete->next;
        p = delete->next;
        delete->next = NULL;
        free(delete);
    }
    printf("%d\n",p->id);
}
int main()
{
    int m;
    scanf("%d",&m);
    while(m--)
    {
        People *head;
        scanf("%d",&N);
        if(N==1)
        {
            printf("1\n");
            continue;
        }
        head = init(); // 初始化循环链表
        function(head);
    }
}