约瑟夫环——循环链表

解题思路:

注意事项:

参考代码:

#include<stdio.h>
#include<stdlib.h>
struct student
{
    int num;
    struct student *pnext;
};
int count=1;    //记录节点数
struct student *creat(struct student *phead,int n)  //创建循环链表
{
    struct student *pnew=NULL,*pend=NULL;
    pnew=pend=(struct student*)malloc(sizeof(struct student));
    pnew->num=1;
    while(n!=count)
    {
        if(count==1)
        {
            pnew->pnext=phead;
            phead=pnew;
        }
        else
        {
            pnew->pnext=pend->pnext;
            pend->pnext=pnew;
            pend=pnew;
        }
        count++;
        pnew=(struct student*)malloc(sizeof(struct student));
        pnew->num=count;
    }
    pend->pnext=phead;  //将最后一个节点与头结点相连形成约瑟夫环
    free(pnew);
    return phead;
}
int f(struct student *phead)
{
    struct student *ptemp=phead,*pre=phead;     //将两个指针指向第一个节点
    pre=pre->pnext;     //pre为删除的前一个节点
    ptemp=pre->pnext;       //要删除的节点
    while(pre!=ptemp)   //当只有一个节点时循环结束
    {
        pre->pnext=ptemp->pnext;    //让前一个节点与后一个节点相连
        free(ptemp);        //释放删除节点
        pre=pre->pnext->pnext->pnext;   //让前一个节点连续前进三位
        ptemp=pre->pnext;   //pre为要删除节点的前一位，前进三位，下一位是下一个要删除的节点
    }
    return pre->num;    //返回数据
}
int main()
{
int n,a;
struct student *phead=NULL;
if(scanf("%d",&n));
phead=creat(phead,n);
a=f(phead);
printf("%d",a);
	return 0;
}