C语言：约瑟夫环问题详解

前言

哈喽，宝子们！本期为大家带来一道C语言循环链表的经典算法题（约瑟夫环）。

目录

• 1.什么是约瑟夫环
• 2.解决方案思路
• 3.创建链表头结点
• 4.创建循环链表
• 5.删除链表
• 6.完整代码实现

  1.什么是约瑟夫环

  据说著名历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿***也不要被人抓到，于是决定了一个自杀方式，41个人拼成一个圆圈，由第一个人开始报数，每报数到第三人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

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

  这道题的原理也是一样的，来看看这道题长什么样吧。

  描述：

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

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

  示例1：

  输入：5, 2

  返回值：3

  说明：

  开始5个人 1，2，3，4，5 ，从1开始报数，1->1，2->2编号为2的人离开。

  1，3，4，5，从3开始报数，3->1，4->2编号为4的人离开。

  1，3，5，从5开始报数，5->1，1->2编号为1的人离开。

  3，5，从3开始报数，3->1，5->2编号为5的人离开。

  最后留下人的编号是3。

  2.解决方案思路

  既然是循环的报数，那我们就index.php/tags-653.html" class="superseo">可以用我们所学过的单链表来解决这道题。

  1. 那假设我们有n个人，就要创建n个节点,首先创建一个节点，然后同时用两个指针指向这个节点，这个节点既是头指针head，也是尾指针ptail
  2. 然后把这个创建的过程用一个函数封装起来，调用函数来创建剩下的几个节点，每次调用完就让ptail的next指针指向我们新创建的节点，然后更新ptail指针的位置。
  3. 此时，我们的节点已经全部创建完成了，但是最重要的一步，就是要让我们的链表形成一个环，最后让尾指针的next指针指向我们的head
  4. 接着就是报数的实现需要有循环，报数要用一个计数器count来记录，当count等于m的时候，就要删除当前这个节点，然后更改头指针和尾指针的位置，最后直到头指针指向自己，此时指针里val的值就是最终留下来的值。

     

  3.创建链表头结点

  //创建头链表
  ListNode* ListBuyNode(int x)
  {
      ListNode* newhead = (ListNode*)malloc(sizeof(ListNode));
      //动态申请内存失败
      if (newhead == NULL)
      {
          exit(1);
      }
      //申请成功
      newhead->val = x;
      newhead->next = NULL;
      return newhead;
  }
  

  4.创建循环链表

  //创建带环链表
  ListNode* CreateCircle(int n)
  {
      //先创建第一个节点
      ListNode* head = ListBuyNode(1);
      ListNode* ptail = head;
      for (int i = 2; i next = ListBuyNode(i);
          ptail = ptail->next;//更新尾节点位置
      }
      //收尾相连，链表成环
      ptail->next = head;
      return ptail;
  }
  

  5.删除链表

  //当链表中只有一个节点的情况就是循环的终止条件
  while (pcur->next != pcur)
  {
      if (count == m)
      {
          //销毁pcur节点
          prev->next = pcur->next;
          free(pcur);
          pcur = prev->next;
          count = 1;
      }
      else
      {
          //此时不需要销毁节点
          prev = pcur;
          pcur = pcur->next;
          count++;
      }
  }
  

  6.完整代码实现

  //定义节点
  struct ListNode
  {
      int val;
      struct ListNode* next;
  };
  typedef struct ListNode ListNode;//类型重定义
  //创建头链表
  ListNode* ListBuyNode(int x)
  {
      ListNode* newhead = (ListNode*)malloc(sizeof(ListNode));
      if (newhead == NULL)
      {
          exit(1);
      }
      newhead->val = x;
      newhead->next = NULL;
      return newhead;
  }
  //创建带环链表
  ListNode* CreateCircle(int n)
  {
      //先创建第一个节点
      ListNode* head = ListBuyNode(1);
      ListNode* ptail = head;
      for (int i = 2; i next = ListBuyNode(i);
          ptail = ptail->next;
      }
      //收尾相连，链表成环
      ptail->next = head;
      return ptail;
  }
  int ysf(int n, int m) 
  {
      //1.根据n创建带环链表
      ListNode* prev = CreateCircle(n);//尾指针
      ListNode* pcur = prev->next;//头指针
      int count = 1;
      //当链表中只有一个节点的情况就是循环的终止条件
      while (pcur->next != pcur)
      {
          if (count == m)
          {
              //销毁pcur节点
              prev->next = pcur->next;
              free(pcur);
              pcur = prev->next;
              count = 1;
          }
          else
          {
              //此时不需要销毁节点
              prev = pcur;
              pcur = pcur->next;
              count++;
          }
      }
      //此时剩下的最后一个节点里的值就是要返回的值
      return prev->val;
  }
  int main()
  {
      //测试用例
      int win=ysf(5, 2);
      printf("%d", win);
      return 0;
  }
  

  ---

  如果对你有所帮助的话，别忘了点赞+关注哟❤️!