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

用户11396661

发布于 2024-12-09 15:00:50

1440

文章被收录于专栏：C++开发C++开发

🏝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(;i<=n;i++)
    {
        ptail->next=BuyNode(i);
        ptail=ptail->next;
    }

    //使链表循环
    ptail->next=phead;

    //返回链表的尾节点
    return ptail;
 }

说明：

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

 ListNode* CreateCircle(int n)
 {
    ListNode* phead=NULL;
    ListNode* ptail=NULL;
    int i=1;
    for(;i<=n;i++)
    {
        if(phead==NULL)
        {
            phead=ptail=BuyNode(i);
        }
        else
        {
            ptail->next=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指针，所以要保存前一个的节点。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-05-05，如有侵权请联系 cloudcommunity@tencent.com 删除

指针