牛客网：约瑟夫问题（链表）

1.问题描述：

2.实现代码：

/
 typedef struct ListNode ListNode;
 ListNode* BuyNode(int x)
 {
    ListNode* node=(ListNode*)malloc(sizeof(ListNode));
    if(node==NULL)
    {
        exit(1);
    }
    node->val=x;
    node->next=NULL;
    return node;
 }
 ListNode* CreateCircle(int n)
 {
    ListNode* phead=BuyNode(1);
    ListNode* ptail=phead;
    int i=2;
    for(;i<=n;i++)
    {
        ptail->next=BuyNode(i);
        ptail=ptail->next;
    }
    ptail->next=phead;
    return ptail;
 }
int ysf(int n, int m ) {
    //根据n创建带环链表
    ListNode *prev=CreateCircle(n);
    ListNode *pcur=prev->next;    
    int count=1;
    while(pcur->next!=pcur)
    {
        if(count==m)
        {
            prev->next=pcur->next;
            free(pcur);
            pcur=prev->next;
            count=1;
        }
        else
        {
            prev=prev->next;
            pcur=pcur->next;
            count++;
        }
    }
    return pcur->val;
}

 3.代码分析：

1.BuyNode函数（创建节点函数，并把节点的val值变为x）：

首先动态申请一块空间，malloc的返回类型是void*,经过强制类型转换以后，赋值给指针node，

然后就是把node->val变为x，node->next变为NULL；

2.CreateCircle函数（用来创建带环链表）：

总共有n个节点，所以要调用n次BuyNode函数，我们先定义第一个节点（可以认为就是头节点），然后第一个节点的val为1，后面的n-1个节点我们通过for循环申请，每次ptail记得变为ptail->next。最后把tail的next的置为phead形成一个环。

最后返回值是ptail，因为这样，我们用完这个函数，我们在其他函数里既可以直接拿到ptail，也可以通过ptail->next直接拿到phead。

3.ysf函数：

首先pcur在节点一的位置，此时报数为1(count)，count记录报数，然后我们进行移动，pcur=pcur->next,当count==m时，我们应该杀了这个人，也就是释放了这个节点。然后把pcur变为prev->next.count变为1.

当pcur->next=pcur,表明只剩下一个节点，这就是我们要找的节点，返回pcur->val。