单链表，尾节点不在指向null，而是尾节点指向第一个节点
image.png

单向循环链表节点

  1.     public class Node
  2.     {
  3.         public int id;
  4.         public Node next;
  5.         public Node(int id)
  6.         {
  7.             this.id = id;
  8.         }
  9.     }

单向循环链表对象类

  1.     public class SingleLoopLinkList
  2.     {
  3.         //先默认创建第一个节点,这个节点不是头结点，是有效节点，默认数据是要修改的
  4.         Node first = new Node(-1);
  5.         public SingleLoopLinkList()
  6.         {
  7.             //初始化的时候默认把第一个节点环起来，环形链表嘛，一个节点也要环起来
  8.             first.next = first;
  9.         }
  11.         //显示节点数据
  12.         public void Show()
  13.         {
  14.             Node temp = first;
  15.             while (true)
  16.             {
  17.                 Console.WriteLine(temp.id);
  18.                 if(temp.next==first)
  19.                 {
  20.                     break;
  21.                 }
  22.                 temp = temp.next;
  23.             }
  24.         }
  26.     }

添加节点

在SingleLoopLinkList类里面的方法
image.png

  1.         //添加节点
  2.         public void Add(Node node)
  3.         {
  4.             if (first.id == -1)
  5.             {
  6.                 //如果第一个节点的数据是默认数据，则这次的添加就是第一次添加数据，就把数据赋值给first
  7.                 first.id = node.id;
  8.             }
  9.             else//到了这一步，就说明第一个first节点已经有了真实数据
  10.             {
  11.                 //当前指针，从first的下一个开始，因为是环形的，不用担心空指针
  12.                 Node cur = first.next;
  13.                 while (true)
  14.                 {
  15.                     if (cur.next == first)//如果当前节点的下一个就是first节点，说明当前节点就是最后一个节点
  16.                     {
  17.                         node.next = first;
  18.                         cur.next = node;
  19.                         break;
  20.                     }
  21.                     cur = cur.next;
  22.                 }
  23.             }
  24.         }

Josephu(约瑟夫)问题

描述

设编号1，2，3，…..，n的n个人围坐在一圈，约定编号为k（1<=k<=n）的人开始从1开始报数，数到m的那个人出列，他的下一位又从1开始报数，数到m的那个人又出列，以此类推，直到所有人出列为止，由此产生一个出队编号的序列。

思路

  1. 用单向环形链表
  2. 用数组取模

    图解

    如上图的 单向环形链表结构
    设k为4，m为3

image.png————image.pngimage.png————image.pngimage.png————image.png
image.png————image.png

代码

在SingleLoopLinkList类里面的方法

在调用Josephu之前，先添加节点

  1. public void Josephu(int k, int m)
  2.         {
  3.             Node temp = first;//辅助指针
  4.             //1.先把temp指向first之前的一个节点，因为first是第一个节点，所以遍历这个链表，找到最后一个节点，就是first前一个节点了
  5.             while (true)
  6.             {
  7.                 if (temp.next == first)//说明temp就是最后一个了
  8.                 {
  9.                     break;
  10.                 }
  11.                 temp = temp.next;
  12.             }
  13.             //2.把temp和first移动k-1次，因为要从第k个开始数，first移动k-1此后，first就是第k个
  14.             for(int i = 0; i < k-1; i++)
  15.             {
  16.                 first = first.next;
  17.                 temp = temp.next;
  18.             }
  19.             //3.循环出圈(直到圈中只有一个节点)：first和temp都同时移动m-1个，自身报数1，移动m-1就是报数m，然后出圈
  20.             while (true)
  21.             {
  22.                 if (temp == first)//说明圈中只有一个节点
  23.                 {
  24.                     break;
  25.                 }
  26.                 //first和temp都同时移动m-1个
  27.                 for(int j = 0; j < m - 1; j++)
  28.                 {
  29.                     first = first.next;
  30.                     temp = temp.next;
  31.                 }
  32.                 //这时候first指向节点就是要出圈的节点
  33.                 Console.WriteLine($"出圈：{first.id}");
  34.                 //这时候要将出圈的first删掉，既然first就是要被删除的节点，单链表删除节点是要用到被删除节点的上一个辅助节点
  35.                 //temp不就是被删除节点first的上一个节点吗
  36.                 first = first.next;
  37.                 temp.next = first;//这两句代码和单链表删除节点的temp.next=temp.next.next一样，temp指被删除节点的上一个节点
  38.             }
  39.             //当到了这里，说明链表就剩一个了，最后一个出圈
  40.             Console.WriteLine($"出圈：{first.id}");
  41.         }