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

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

使用遍历方法

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

步骤

• 步骤1 − 首先，我们需要导入fmt包。

• 步骤2 − 现在，初始化一个节点结构，并在其中分配两个变量。第一个变量存储整数数据，而第二个指针变量存储下一个节点的地址。

• 步骤3 − 现在，创建一个不同的函数称为countNodes()。此函数接受要遍历的列表作为参数。

• 步骤4 − 在函数内部，将0存储到count变量中，并将列表的头节点存储到current变量中。

• 步骤5 − 使用for循环迭代链表，并在达到新节点时增加count变量。然后返回此变量。

• 步骤6 − 开始main()函数。在main()函数内部，使用不同的节点head、node2、node3等将它们链接在一起，方法是将下一个节点的地址存储到当前节点的下一个元素中。

• 步骤7 − 现在调用countNodes()函数，并将链表的头节点作为参数传递给函数。

• 步骤8 − 进一步，将函数获取的count存储在不同的变量中，并使用fmt.Println()函数将其打印到屏幕上。

示例

以下示例演示了如何开发一个Go语言程序，使用遍历方法计算循环链表中节点的数量。

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循环查找算法

在这个方法中，我们将编写一个Go语言程序，通过使用Floyd循环查找算法来计算循环链表中节点的数量。该算法使用两个指针变量，其中一个变量每次移动一个节点，而另一个变量每次移动两个节点。

步骤

• 步骤1 - 首先，我们需要导入fmt包。然后创建一个名为struct的节点，并在其中存储一个变量以存储数据和一个指针以存储下一个节点的地址。

• 步骤2 - 创建一个名为countNodes()的函数来计算给定列表中节点的数量。创建两个指针变量，称为slow和fast，并将头节点的地址存储在它们中。

• 步骤3 - 使用循环遍历链表，直到快指针到达链表的末尾或者到达慢指针。如果发生这种情况，则没有循环，所以返回零作为列表中节点的数量。

• 步骤4 - 为了计算节点的数量，再次遍历链表，递增计数变量并将慢指针向前移动一步。

• 步骤5 - 一旦慢指针再次到达快指针，我们就计算出循环中的所有节点。将计数变量作为链表中的节点数返回。

• 步骤6 - 现在，启动main()函数。在main()函数内部，通过使用节点结构初始化头节点并给其赋值。

• 步骤7 - 以这种方式创建不同的节点，并将它们与头节点链接在一起。通过将头节点作为参数传递给countNodes()函数来调用该函数。

• 步骤8 - 将函数得到的结果存储在一个变量中，并将其打印到屏幕上。

示例

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

package main

import "fmt"

type Node struct {
   data int
   next *Node
}

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

   // Detect the presence of a loop
   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("Number of nodes present in the circular linked list are:", countNodes(head))
}

输出

Number of nodes present in the circular linked list are: 3

结论

我们成功编译并执行了一个Go语言程序，用于计算循环链表中节点的数量，并给出了示例。这里我们使用了两个程序。在第一个程序中，我们使用遍历的方法，而在第二个程序中，我们使用Floyd循环方法来实现结果。