牛客网：环形链表的约瑟夫问题

🎁个人主页：我们的五年

🔍系列专栏：每日一练

🌷追光的人，终会万丈光芒

目录

🏝1.问题描述：

🏝2.实现代码：

🏝1.问题描述：

前言：

约瑟夫问题 有很多种解决办法，下面我们用链表进行解题

题目链接：环形约瑟夫问题（直接点击就可以了）

🏝2.实现代码：

❗️注意：

//题目是编写函数，外部已经存在节点结构体

//如：

struct ListNode{

        int val;

        struct ListNode* next;

};

//另外我对struct ListNode重命名为ListNode

typedef struct ListNode ListNode;

⛳️1.创建节点的函数：

 ListNode* BuyNode(int x)
 {
    
    ListNode *node=(ListNode*)malloc(sizeof(ListNode));
    
    if(node==NULL)   //对动态申请进行判空处理
    {
        exit(1);
    }
    //对节点里的成员进行初始化
    node->val=x;
    node->next=NULL;
    //返回指向节点的指针
    return node;
 }

⛳️2.创建环形链表函数：

ListNode* CreateCircle(int n)
 {
    //创建头节点
    ListNode* phead=BuyNode(1);
    //创建
    ListNode* ptail=phead;
    //创建另外的n-1个节点
    int i=2;
    for(;inext=BuyNode(i);
        ptail=ptail->next;
    }
    //使链表循环
    ptail->next=phead;
    //返回链表的尾节点
    return ptail;
 }

 说明：

如果不在循环外面申请头结点，那么代码就会变成这样：

 ListNode* CreateCircle(int n)
 {
    ListNode* phead=NULL;
    ListNode* ptail=NULL;
    int i=1;
    for(;inext=BuyNode(i);
            ptail=ptail->next;
        }
    }
    ptail->next=phead;
    return ptail;
 }

 这样在循环里进行判断，会增加时间复杂度。

⛳️3.主函数

int ysf(int n, int m ) {
    // 创建带环链表，prev指向为尾节点，pcur指向头结点
    //此时pcur报数为1
    ListNode* prev=CreateCircle(n);
    ListNode* pcur=prev->next;
    int count=1;
    //结束时，只剩下一个节点，那么pcur->next=pcur
    while(pcur->next!=pcur)
    {
        //如果count为m时，就要进行删除操作
        if(count==m)
        {
            prev->next=pcur->next;
            free(pcur);
            pcur=prev->next;
            count=1;
        }
        //不是m，向后移，count++
        else
        {
            pcur=pcur->next;
            prev=prev->next;
            count++;
        }
    }
    int end=pcur->val;
    //对最后一个节点进行释房
    free(pcur);
    pcur=NULL;
    
    return end;
}

用两个指针prev和pcur的目的是，如果释放pcur时，要拿到前一个节点，使前一个节点的next指针指向pcur的next指针，所以要保存前一个的节点。