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

循环链表是一种链式数据结构，与单链表和双链表不同的是，循环链表会将其尾结点的指针指向头结点，从而使整个链表形成一个环。在循环链表中，节点数量的计算并不像单链表那么简单，本文就将介绍如何用Golang实现计算循环链表中节点数的程序。

初识循环链表

循环链表的实现方式与单向链表类似，但是需要注意的是，循环链表的尾节点指向头节点，且头节点指向第一个数据节点。在程序中，我们通常用一个结构体表示链表的节点：

type ListNode struct {
    Data interface{} // 数据域
    Next *ListNode   // 指针域，指向下一个节点
}

循环链表需要在创建时将头节点的指针域指向自身，以形成一个循环：

func NewCircularList() *ListNode {
    head := &ListNode{
        Data: nil,
        Next: nil,
    }
    head.Next = head
    return head
}

创建了循环链表后，就可以像单链表一样在其中加入和删除节点：

func (head *ListNode) AppendNode(node *ListNode) {
    cur := head
    for cur.Next != head {
        cur = cur.Next
    }
    cur.Next = node
    node.Next = head
}

func (head *ListNode) DeleteNode(node *ListNode) {
    cur := head
    for cur.Next != node {
        cur = cur.Next
    }
    cur.Next = node.Next
}

这里只演示了添加和删除操作，其他常用操作如查找和插入等都可以在单链表中找到实现方式。

计算循环链表中节点数

由于循环链表的结构跟单链表不同，我们不能像单链表那样，通过定义一个计数器和一个指针遍历整个链表来计算节点数量。而是需要用一个快指针和一个慢指针共同遍历链表，当两个指针相遇时，慢指针所在位置即为链表的尾结点，而快指针所在位置即为链表的头结点，通过这种方式就可以计算得到循环链表的节点数量。

以下是用Golang实现计算循环链表中节点数的程序：

func CountNodes(head *ListNode) int {
    if head == nil {
        return 0
    }
    slow, fast := head, head
    count := 0
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        count++
        if slow == fast {
            break
        }
    }
    return count
}

在程序中，我们用两个指针slow和fast分别指向链表的头结点，然后让fast指针每次向前移动两个节点，slow指针每次向前移动一个节点，当fast指针指向链表尾部时，slow指针指向链表的尾结点。

为了防止程序死循环，我们在每次移动fast指针和slow指针之前先判断两个指针是否相遇，若已经相遇，则说明链表中存在环，这时我们就可以直接退出循环。

最后返回计数器即可得到循环链表中节点的数量。

完整程序

以下是一个完整的用Golang实现计算循环链表中节点数的程序：

package main

import "fmt"

type ListNode struct {
    Data interface{} // 数据域
    Next *ListNode   // 指针域，指向下一个节点
}

// 创建循环链表
funcNewCircularList() *ListNode {
    head := &ListNode{
        Data: nil,
        Next: nil,
    }
    head.Next = head
    return head
}

// 添加节点
func (head *ListNode) AppendNode(node *ListNode) {
    cur := head
    for cur.Next != head {
        cur = cur.Next
    }
    cur.Next = node
    node.Next = head
}

// 删除节点
func (head *ListNode) DeleteNode(node *ListNode) {
    cur := head
    for cur.Next != node {
        cur = cur.Next
    }
    cur.Next = node.Next
}

// 计算循环链表中节点数量
func CountNodes(head *ListNode) int {
    if head == nil {
        return 0
    }
    slow, fast := head, head
    count := 0
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        count++
        if slow == fast {
            break
        }
    }
    return count
}

func main() {
    // 创建循环链表
    head := NewCircularList()
    // 添加节点，节点数据为1、2、3、4、5
    for i := 1; i <= 5; i++ {
        node := &ListNode{
            Data: i,
            Next: nil,
        }
        head.AppendNode(node)
    }
    // 输出循环链表的节点数量
    fmt.Println("节点数量：", CountNodes(head))
}

在main函数中，我们先创建一个循环链表head，然后向其中加入5个节点，最后计算出循环链表中节点的数量并输出。