计算循环链表中节点数的 Golang 程序

在计算机科学中，循环链表是一种重要的数据结构，用于高效地管理内存和数据。循环链表是一种链表，其中列表的最后一个节点指向列表的第一个节点，从而创建一个循环。

使用遍历方法

在此方法中，我们将编写一个 Golang 程序，通过遍历它来计算循环链表中节点数。

算法

步骤 1 - 首先，我们需要导入 fmt 包。
步骤 2 - 现在，初始化一个节点结构并为其分配两个变量。第一个变量存储整数数据，而第二个指针变量存储下一个节点的地址。
步骤 3 - 现在，创建一个名为 countNodes() 的不同函数。此函数将接受要遍历的列表作为参数。
步骤 4 - 在函数中，将 0 存储到计数变量中，并将列表的头节点存储到当前变量中。
步骤 5 - 使用 for 循环遍历链表，并在每次到达新节点时增加计数变量。进一步返回此变量。
步骤 6 - 启动 main() 函数。在 main() 函数内初始化名为 head、node2、node3 等不同的节点，并通过将下一个节点的地址存储到当前节点的下一个元素来将它们链接在一起。
步骤 7 - 现在调用 countNodes() 函数，并将链接列表的头节点作为参数传递给该函数。
步骤 8 - 进一步，将函数获得的计数存储到其他变量中，并通过使用 fmt.Println() 函数将其打印到屏幕上。

示例

以下示例演示如何编写 Golang 程序，通过使用遍历方法计算循环链表中的节点数。

package main

import "fmt"

type Node struct {
   data int
   next *Node
}

func countNodes(head *Node) int {
   count := 0
   current := head

   for current != nil && current.next != head {
      count++
      current = current.next
   }

   if current == head {
      count++
   }
   return count
}

func main() {
   head := &Node{data: 1}
   node2 := &Node{data: 2}
   node3 := &Node{data: 3}
   node4 := &Node{data: 4}
   head.next = node2
   node2.next = node3
   node3.next = node4
   node4.next = head

   count := countNodes(head)
   fmt.Println("The number of nodes in the given circular linked list are:", count)
}

输出

The number of nodes in the given circular linked list are: 3

使用 Floyd 循环查找算法

在此方法中，我们将编写一个 Golang 程序，通过使用 Floyd 循环查找算法计算循环链表中存在的节点数。此算法使用两个指针变量，一个变量一次移动一个节点，而另一个变量一次移动两个节点。

算法

第一步 − 首先，我们需要导入 fmt 包。然后创建一个名为 struct 的节点，其中存储一个变量以存储数据并存储下一个节点的地址。
第二步 − 创建名为 countNodes() 的函数来计算给定列表中存在的节点数。创建两个指针变量 slow 和 fast，并将它们的地址存储到头节点中。
第三步 − 使用循环遍历链表，直到快指针到达列表的末尾或到达慢指针。如果发生这种情况，则没有循环，因此将列表中的节点数返回为零。
第四步 − 为了计算节点数。再次通过链表进行遍历并递增 count 变量并将慢指针向前移动一步。
第五步 − 一旦慢指针再次到达快指针，我们就统计循环中的所有节点。将 count 变量作为链表中的节点数返回。
第六步 − 现在，开始 main() 函数。在 main() 中使用 node struct 初始化头节点并为其分配值。
第七步 − 以此方式创建不同的节点并将它们与头节点链接在一起。通过将头节点作为函数的参数传递来调用 countNodes() 函数。
第八步 − 将函数获得的结果存储在变量中并在屏幕上打印它。

示例

以下示例解释了如何使用 Floyd 循环查找算法创建 go 语言程序来计算循环链表中的节点数。

package main

import "fmt"

type Node struct {
   data int
   next *Node
}

func countNodes(head *Node) int {
   slow := head
   fast := head

   // 检测是否存在环
   for fast != nil && fast.next != nil {
      slow = slow.next
      fast = fast.next.next
      if slow == fast {
         break
      }
   }

   count := 0
   if fast != nil && fast.next != nil {
      slow = slow.next
      count++
      for slow != fast {
         count++
         slow = slow.next
      }
   }
   return count
}

func main() {
   head := &Node{data: 1}
   head.next = &Node{data: 2}
   head.next.next = &Node{data: 3}
   head.next.next.next = head

   fmt.Println("循环链表中的节点数为：", countNodes(head))
}