示意图

image.png

注意

  1. 头节点有数据
  2. 最后一个节点的 next 指向 头节点 head， 构成一个环
  3. 删除节点
    1. 双指针，一前一后，前面的用来比较判断，后一个用来操作删除（单向的链表无法自删除，需要借助辅助节点）
    2. 只有一个节点，next 指向 nil
    3. 删除的是第一个节点，则需要重新修改 head 的指向

image.png

代码

  1. // 环形单向链表
  2. package main
  4. import "fmt"
  6. type CatNode struct {
  7.     no   int
  8.     name string
  9.     next *CatNode
  10. }
  12. func insertNode(head *CatNode, newCatNode *CatNode) {
  13.     // 1. 处理第一个节点(头节点有值)
  14.     if head.next == nil {
  15.         head.no = newCatNode.no
  16.         head.name = newCatNode.name
  17.         head.next = head // 构成环形
  18.         fmt.Printf("第一个节点： 猫： %v 加入环形链表 \n", newCatNode.name)
  19.         return
  20.     }
  22.     // 2. 处理别的节点
  23.     // 找到最后的节点
  24.     // 定义临时变量
  25.     temp := head
  26.     for {
  27.         if temp.next == head {
  28.             break
  29.         }
  30.         temp = temp.next
  31.     }
  32.     // 加入到链表
  33.     temp.next = newCatNode
  34.     newCatNode.next = head
  35. }
  37. // 按顺序插入
  38. func insertNode02(head *CatNode, newCatNode *CatNode) {
  39.     fmt.Println("insertNode02 - head: ", head)
  40.     // 1. 处理第一个节点(头节点有值)
  41.     if head.next == nil {
  42.         head.no = newCatNode.no
  43.         head.name = newCatNode.name
  44.         head.next = head // 构成环形
  45.         fmt.Printf("第一个节点： 猫： %v 加入环形链表 \n", newCatNode.name)
  46.         return
  47.     }
  49.     // 2. 处理别的节点
  50.     // 定义临时变量
  51.     temp := head
  52.     flag := true
  53.     for {
  54.         if temp.no == newCatNode.no {
  55.             fmt.Printf("节点： %v ,  已经存在，不允许加入", newCatNode.no)
  56.             flag = false
  57.             break
  58.         } else if temp.next == head {
  59.             break
  60.         } else if temp.next.no > newCatNode.no {
  61.             break
  62.         } else if temp.next.no == newCatNode.no {
  63.             fmt.Printf("节点： %v ,  已经存在，不允许加入", newCatNode.no)
  64.             flag = false
  65.             break
  66.         }
  67.         temp = temp.next
  68.     }
  69.     // 加入到链表
  70.     // temp.next = newCatNode
  71.     // newCatNode.next = head
  73.     if !flag {
  74.         fmt.Println("不能插入节点")
  75.         return
  76.     } else {
  78.         // 最后一个节点后插入
  79.         if temp.next == head {
  80.             temp.next = newCatNode
  81.             newCatNode.next = head
  82.         } else {
  83.             // 中间节点插入
  84.             newCatNode.next = temp.next
  85.             temp.next = newCatNode
  86.         }
  88.     }
  89. }
  91. // 删除节点
  92. func delNode(head *CatNode, id int) *CatNode {
  93.     // 这里的头节点是有值的
  94.     fmt.Println("delNode - head: ", head)
  95.     temp := head
  96.     helper := head // helper 指向 head 的上一个节点， 即尾节点
  98.     // 1. 空链表
  99.     if temp.next == nil {
  100.         fmt.Println("空链表")
  101.         return head
  102.     }
  104.     // 2. 只有一个
  105.     if temp.next == head {
  106.         temp.next = nil // 没有任何指向就会被gc回收，即删除
  107.         return head
  108.     }
  110.     // 3. 将 helper 指向最后
  111.     for {
  112.         if helper.next == head {
  113.             break
  114.         }
  115.         helper = helper.next
  116.     }
  118.     // 4. 两个及以上节点
  119.     flag := true
  120.     for {
  121.         if temp.next == head {
  122.             // 只是比较，还没有执行删除操作
  123.             break
  124.         }
  125.         if temp.no == id {
  126.             if temp == head {
  127.                 // 删除的是头节点, 修改头节点的指向
  128.                 head = temp.next
  129.             }
  130.             helper.next = temp.next
  131.             flag = false
  132.             fmt.Printf("猫: no: %v 被移除链表了 \n", id)
  133.             break
  134.         }
  135.         temp = temp.next     // 移动 - 比较
  136.         helper = helper.next // 移动 - 执行删除
  137.     }
  138.     // 这里要增加一次比较
  139.     if flag {
  140.         if temp.no == id {
  141.             // temp 就是 要删除的节点
  142.             helper.next = temp.next
  143.         } else {
  144.             fmt.Println("没有找到要删除的节点id: ", id)
  145.             return head
  146.         }
  147.     }
  148.     return head
  149. }
  151. // 显示所有节点
  152. func showNode(head *CatNode) {
  153.     temp := head
  154.     if temp.next == nil {
  155.         fmt.Println("空链表")
  156.         return
  157.     }
  158.     for {
  159.         fmt.Printf("[猫: no: %v, name: %v] => ", temp.no, temp.name)
  160.         if temp.next == head {
  161.             break
  162.         }
  163.         temp = temp.next
  164.     }
  165.     fmt.Println()
  166. }
  168. func main() {
  169.     // 初始化环形链表头节点
  170.     head := &CatNode{}
  171.     cat1 := &CatNode{
  172.         no:   1,
  173.         name: "tom1",
  174.     }
  175.     cat2 := &CatNode{
  176.         no:   2,
  177.         name: "tom2",
  178.     }
  179.     cat3 := &CatNode{
  180.         no:   3,
  181.         name: "tom3",
  182.     }
  183.     insertNode02(head, cat1)
  184.     insertNode02(head, cat3)
  185.     insertNode02(head, cat2)
  186.     insertNode02(head, cat3)
  188.     fmt.Println("显示")
  189.     showNode(head)
  191.     fmt.Println("删除 1")
  192.     // 删除之后，重新制定 头节点 head
  193.     head = delNode(head, 1)
  195.     showNode(head)
  196. }
  198. /*
  199. insertNode02 - head:  &{0  <nil>}
  200. 第一个节点： 猫： tom1 加入环形链表
  201. insertNode02 - head:  &{1 tom1 0xc00004e3c0}
  202. insertNode02 - head:  &{1 tom1 0xc00004e420}
  203. insertNode02 - head:  &{1 tom1 0xc00004e400}
  204. 节点： 3 ,  已经存在，不允许加入不能插入节点
  205. 显示
  206. [猫: no: 1, name: tom1] => [猫: no: 2, name: tom2] => [猫: no: 3, name: tom3] =>
  207. 删除 1
  208. delNode - head:  &{1 tom1 0xc00004e400}
  209. 猫: no: 1 被移除链表了
  210. [猫: no: 2, name: tom2] => [猫: no: 3, name: tom3] =>
  211. */

👉约瑟夫问题

Josephu 问题
Josephu 问题为：设编号为 1，2，… n的n个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1开始报数，数到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
提示
用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束。

解题示意图：

image.png
image.png
image.png
image.png
image.png

代码实现

  1. // 约瑟夫问题 (丢手绢)， 单向环形链表
  3. package main
  5. import "fmt"
  7. type Boy struct {
  8.     No   int
  9.     Next *Boy
  10. }
  12. // 编写函数 构成 单向环形链表
  13. // num 表示小孩的个数
  14. // *Boy 返回该
  15. func AddBoy(num int) *Boy {
  16.     first := &Boy{}
  17.     curBoy := &Boy{}
  19.     if num < 1 {
  20.         fmt.Println("num的值不对")
  21.         return first
  22.     }
  24.     for i := 1; i <= num; i++ {
  25.         // 生成 boy
  26.         boy := &Boy{
  27.             No: i,
  28.         }
  30.         if i == 1 {
  31.             first = boy
  32.             curBoy = boy
  33.             curBoy.Next = first
  34.         } else {
  35.             curBoy.Next = boy
  36.             curBoy = boy
  37.             curBoy.Next = first
  38.         }
  39.     }
  40.     return first
  41. }
  43. // 显示单向环形链表
  44. func show(first *Boy) {
  45.     if first.Next == nil {
  46.         fmt.Println("空链表")
  47.         return
  48.     }
  50.     curBoy := first
  51.     for {
  52.         fmt.Printf("[编号： %v] => ", curBoy.No)
  53.         if curBoy.Next == first {
  54.             break
  55.         }
  56.         curBoy = curBoy.Next
  57.     }
  58.     fmt.Println()
  59. }
  61. // 游戏开始了， 结束后 first 重新赋值， 状态归位（否则会引发问题）， 以便后续操作
  62. func PlayGame(first *Boy, startNo int, countNum int) *Boy {
  63.     if first.Next == nil {
  64.         fmt.Println("空链表")
  65.         return first
  66.     }
  68.     // 定义辅助指针, 指向最后一个节点
  69.     tail := first
  70.     for {
  71.         if tail.Next == first {
  72.             break
  73.         }
  74.         tail = tail.Next
  75.     }
  77.     // 定位到初始节点 赋给first； tail 跟着移动到 first 后面
  78.     for i := 1; i <= startNo-1; i++ {
  79.         first = first.Next
  80.         tail = tail.Next
  81.     }
  83.     // for循环处理方式
  84.     // for {
  85.     //     // 找到要删除的节点,
  86.     //     for i := 1; i <= countNum-1; i++ {
  87.     //         first = first.Next
  88.     //         tail = tail.Next
  89.     //     }
  91.     //     // 执行删除
  92.     //     fmt.Printf("编号： %v 出列\n", first.No)
  93.     //     first = first.Next
  94.     //     tail.Next = first
  95.     //     // 可以编写回调函数
  97.     //     if first == tail {
  98.     //         break
  99.     //     }
  100.     // }
  102.     // 以下是递归调用的方式
  103.     first = delNode(first, tail, countNum)
  104.     fmt.Printf("编号： %v 是最后一个\n", first.No)
  105.     return first
  106. }
  108. // 递归调用
  109. func delNode(first *Boy, tail *Boy, countNum int) *Boy {
  110.     // 1. 找到要删除的节点,
  111.     for i := 1; i <= countNum-1; i++ {
  112.         first = first.Next
  113.         tail = tail.Next
  114.     }
  116.     // 2. 执行删除
  117.     fmt.Printf("编号： %v 出列\n", first.No)
  118.     first = first.Next
  119.     tail.Next = first
  121.     // 向临界条件逼近 first.Next == first, 或者 first == tail
  122.     if first.Next == first {
  123.         // 表示已经剩最后一个了,
  124.         return first
  125.     }
  126.     boy := delNode(first, tail, countNum)
  127.     // 返回最后剩下的
  128.     return boy
  129. }
  131. func main() {
  132.     first := AddBoy(5)
  133.     show(first)
  134.     fmt.Println("开始...")
  135.     first = PlayGame(first, 2, 3)
  136.     fmt.Println("------ 结束了， 显示剩余的：------")
  137.     show(first)
  138. }
  140. /*
  141. [编号： 1] => [编号： 2] => [编号： 3] => [编号： 4] => [编号： 5] =>
  142. 开始...
  143. 编号： 4 出列
  144. 编号： 2 出列
  145. 编号： 1 出列
  146. 编号： 3 出列
  147. 编号： 5 是最后一个
  148. ------ 结束了， 显示剩余的：------
  149. [编号： 5] =>
  150. */