环形链表的约瑟夫问题

前言

大家好呀，我是Humble，今天要分享的内容是环形链表的约瑟夫问题

说到链表，约瑟夫问题（约瑟夫环）绝对是一个经典的算法题，下面就让我们一起看一下吧~

正文开始前，我们先看一个小小的故事，借此引出主题，如果能勾起大家学习的兴趣就太好啦~

据说历史上有过这样的故事：在罗马人占领乔塔帕特后，39个犹太人与约瑟夫及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被人抓到，于是决定了一个自杀方式：

41个人排成⼀圈，由第1个人开始报数，每报数到第3人，该人就必须自杀，然后再由下一个人重新报数，直到所有人都自杀身亡为止

然而约瑟夫和他的朋友并不想遵从。约瑟夫要他的朋友先假装遵从，他将朋友与自己安排在
第16个与第31个位置，于是逃过了这场死亡游戏

好，看完这个故事，不知道你有什么感想？下面我们回归正题，来做一下有这段轶事衍生出的约瑟夫问题吧~

正文

环形链表的约瑟夫问题_牛客题霸_牛客网 (nowcoder.com)

题目描述：

编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开

下一个人继续从 1 开始报数。

n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

对于这道题目，Humble的思路是：
1.根据n来创建不带头的单向循环链表

2.逢m删除当前节点

实现的代码如下：

//为了方便，我们另外封装了两个函数，
//一个用来申请新的节点，一个用来创建不带头单向循环链表~

typedef struct ListNode ListNode;//偷个懒，将struct ListNode重命名为ListNode,嘿嘿

ListNode* BuyNode(int x)
{
   ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));

   newNode->val = x;
   newNode ->next = NULL;
   
   return newNode;
}

ListNode* createlist(int n)
{
    ListNode* phead = BuyNode(1);
    ListNode* ptail = phead;
    for (int i =2;i<=n;i++)
    {
        ptail->next = BuyNode(i);
        ptail = ptail->next;
    }
     ptail->next = phead;//让链表构成环

     return ptail;//返回尾节点

}

int ysf(int n, int m )
 {
   ListNode* prev = createlist(n);//前驱，因为链表是循环的所以初始放在尾节点
   ListNode * head = prev->next;
   ListNode* pcur  = head;

   int count = 1;//计数;

   while (pcur->next != pcur)
   {
       if(count == m)
       {
        prev->next = pcur->next;
        free(pcur);
        pcur =  prev->next;
        count = 1;
       }
        
        else 
        {
          prev  = pcur;
          pcur = pcur->next;
          count++;
        }

   }

//循环结束后，此时的pcur节点就是幸存下来的唯一的节点了
return pcur->val; //输出幸存者的编号
  
}

运行结果如下：