报数问题——循环链表实现

解题思路:

    1、创建一个长度为n循环链表。先创建一个单向链表，然后令头结点和尾结点的next指针都指向首结点，编号为1的结点为首结点。

    2、从首结点p开始报数，用循环让p移动到需要删除的结点的前一个结点，则需删除的结点为p->next。代码如下：

/*让p移动到需要移除的结点的前一个*/
        for (int i = 1; i < CYCLE-1; i++)
        {
            p = p->next;
        }
/*在本题中只需要报数到3，所以上述指针p只需要从报数为1的结点移动到报数为2的结点，上述代码可以直接简写为p = p->next;*/

    3、用指针first记录报数为1的结点，用free()释放报数为3的结点，然后将first赋给p。（first相当于一个中间变量）

代码：    
        first = (p->next)->next;/*下一轮报数为1的结点*/
        free(p->next);      /*释放掉报数为3的结点*/
        p->next = first;    /*当前报数为2的结点的下一个结点为下一轮报数为1的结点*/
        p = first;       /*新一轮报数*/

    4、循环第2、3步骤，直到链表只剩一个结点（p->next = p）。

    5、输出最后一个结点的编号，然后释放该结点。

注意事项: 别忘记用free()释放最后一个结点

参考代码:

#include<stdio.h>
#define CYCLE 3   /*需退出的报数值*/

typedef struct people
{
    int number;
    struct people* next;
} Node;

/**********创建长度为n的循环链表**************/
Node* CreatLink(int n)
{
    /*头结点，不计入循环，最开始指向编号为1的结点，报数开始后释放*/
    Node *head = NULL;
    head = (Node *)malloc(sizeof(Node));
    
    Node * newnode, * current;
    current = head;
    for (int i = 1; i <= n; i++)
    {
        newnode = (Node*)malloc(sizeof(Node));
        newnode->number = i;
        current->next = newnode;/*插入结点*/
        current = newnode;
    }
    
    /*创建为循环链表，最后一个结点与头结点的*next指针指向同一个结点*/
    newnode->next = head->next;
    return head;
}

/**********移除报数为3的结点**************/
void Remove(Node* head)
{
    Node* first;
    first = head->next;
    free(head);/*释放头结点*/
    
    /*first用于记录报数为1的结点*/
    Node* p = first;
    while (p->next != p)
    {
        /*让p移动到需要移除的结点的前一个*/
        for (int i = 1; i < CYCLE-1; i++)
        {
            p = p->next;
        }
        
        first = (p->next)->next;/*下一轮报数为1的结点*/
        free(p->next);      /*释放掉报数为3的结点*/
        p->next = first;    /*当前报数为2的结点的下一个结点为下一轮报数为1的结点*/
        p = first;       /*新一轮报数*/
    }
    
    printf("%d\n", p->number);     /*输出最后一个人的编号*/
    free(p);             /*释放最后一个结点*/
}

int main()
{
    int num;
    scanf("%d", &num);        /*初始人数*/
    Node *PeopleLink;
    PeopleLink = CreatLink(num);    /*创建循环链表*/
    Remove(PeopleLink);        /*移除报数为3的人，输出最后一个人的初始编号*/
    return 0;
}