【出圈】 （C语言代码）

解题思路:

看完题目，嗯，一个圈子，大家轮流报数退出，直到剩下一个人为止。

这不就是一个循环链表嘛！！在创建链表的时候数据域里存放他们的序号，指针域存放他们的下一个序号，链表的尾节点指向链表的头节点，就是题目说的那个小圈圈啦

然后我们设置一个计数器，当报到计数器设定的数的时候，就把那个链表节点释放掉

注意事项:

注意链表的插入方式，用头插法和尾插法创建的链表的遍历顺序会不一样哦

参考代码:

#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
    int aa;                       //数据域
    struct Node *next;            //指针域
}LNode, *PNode;

//采用尾插法，保证循环圈的顺序是从小到大 
PNode ChaRu(LNode *h1, int n)
{
    LNode *p1;
    p1 = (LNode*)malloc(sizeof(LNode));
    p1->next = h1->next;
    h1->next = p1;
    p1->aa = n;
    return p1;            //更新p指针位置
}

int BaoShu(LNode *h2, int m)
{
    int count = 1, xx;                     //count是计数器，xx用来保存最后剩下的那一个人的序号
    LNode *p2 = h2->next, *del = NULL;
//删除报数的链表节点并一直报下去，直到只剩一个元素 
    while (p2->next != p2){
        //把m-1节点与m+1节点连接起来，删除m节点，因为单向循环链表无法找到前驱结点，故只能在m-1节点动手
        if (count == m - 1){
            del = p2->next;
            p2->next = del->next;
            p2 = del->next;
            free(del);
            count = 1;
            continue;
        }
        p2 = p2->next;
        count++;
    }
    xx = p2->aa;
    free(p2);
    //释放掉申请的内存，防止内存泄漏（当存在内存泄漏的情况程序可能会终止运行）
    return xx;
}

int main(void)
{
    int nn, mm, i;
    LNode *h, *p;

    while (scanf("%d%d", &nn, &mm) == 2){
        h = (PNode)malloc(sizeof(LNode));
        p = h;
        h->next = h;
        h->aa = nn;
    //创建循环圈子并对圈子中的元素赋值 
        for (i = 1; i < nn; i++){
            p = ChaRu(p, i);                //更新p指针的位置
        }
        printf("%d\n", BaoShu(h, mm));
    }
    return 0;
}