Golang 逆转循环链表

在本文中，我们将学习如何使用递归和迭代方法创建一个 Golang 程序来逆转循环链表。循环链表是一种链表类型，其中列表中的最后一个节点指向第一个节点，形成一个循环。它可以用于实现循环缓冲区或循环调度算法。

语法

func reverseList(head **Node){…}

reverseList()函数用于反转一个循环链表。它接受一个参数作为指向头结点地址的指针的值。

func reverseList(current, prev, head *Node) *Node {…}

reverseList()函数用于反转循环链表。它以第一个非头节点作为当前节点参数，nil作为前一个节点参数以及链表的头节点参数。

方法1

在这种方法中，我们将使用迭代方法定义reverseList()函数，用于反转循环链表。

步骤

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

• 步骤2 - 然后，初始化一个节点结构，用于表示循环链表的元素。每个节点都有一个值和一个指向下一个节点的指针。

• 步骤3 - 现在，创建一个nodeAdd()函数，将新节点添加到循环链表中。它使用给定的值创建一个新节点，并将其插入到头节点之后。

• 步骤4 - 定义printLinkedList()函数，打印循环链表中所有节点的值。

• 步骤5 - 现在，创建一个名为reverseList()的函数。它用于反转循环链表中节点的顺序。

• 步骤6 - 此函数接受指向列表当前头部的指针，遍历列表中的节点，并交换它们的下一个指针以反转顺序。

• 步骤7 - 开始main()函数。在main()函数内部，将几个节点插入循环链表中。

• 步骤8 - 现在，调用reverseList()函数，并将头节点指针的值作为参数传递给该函数。

• 步骤9 - 此外，使用fmt.Println()函数在屏幕上打印已反转的循环链表。

示例

以下是使用迭代方法反转循环链表的Go语言程序

package main

import "fmt"

type Node struct {
   value int
   next  *Node
}

func nodeAdd(head **Node, value int) {
   newNode := &Node{value, nil}

   if *head == nil {
      *head = newNode
      newNode.next = *head
   } else {
      newNode.next = (*head).next
      (*head).next = newNode
      *head = newNode
   }
}

func printLinkedList(head *Node) {
   if head == nil {
      fmt.Println("List is empty!")
      return
   }

   fmt.Print(head.value, " ->")
   for current := head.next; current != head; current = current.next {
      fmt.Print(current.value, " ->")
   }
   fmt.Println(head.value)
}

func reverseList(head **Node) {
   if *head == nil {
      return
   }

   current := (*head).next
   prev := *head
   for current != *head {
      next := current.next
      current.next = prev
      prev = current
      current = next
   }

   (*head).next = prev
   *head = prev
}

func main() {
   var head *Node

   nodeAdd(&head, 5)
   nodeAdd(&head, 3)
   nodeAdd(&head, 6)
   nodeAdd(&head, 2)
   nodeAdd(&head, 4)

   fmt.Println("Initial linked list:")
   printLinkedList(head)

   reverseList(&head)

   fmt.Println("Reversed linked list:")
   printLinkedList(head)
}

输出

Initial linked list:
4 -> 5 -> 3 -> 6 -> 2 -> 4
Reversed linked list:
2 -> 6 -> 3 -> 5 -> 4 -> 2

方法2

在这个示例中，我们将使用递归方法定义一个reverseList()函数，用于将循环链表反转。

步骤

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

• 步骤2 − 然后，初始化一个节点结构来表示循环链表的元素。每个节点都有一个值和指向下一个节点的next指针。

• 步骤3 − 现在，创建一个nodeAdd()函数，它将新节点添加到循环链表中。它创建一个具有给定值的新节点，并将其插入到头节点之后。

• 步骤4 − 定义printList()函数来打印循环链表中所有节点的值。

• 步骤5 − 现在，创建一个名为reverseList()的函数。它使用一个递归辅助函数来遍历和反转链表。

• 步骤6 − 如果当前节点等于头节点，则更新next指针以指向列表的新节点。

• 步骤7 − 否则，递归调用函数，其中下一个节点作为当前节点，当前节点作为前一个节点，头节点仍然是头节点。

• 步骤8 − 在每个递归调用中，更新当前节点的next指针以指向前一个节点。

• 步骤9 − 最后，初始头节点作为列表的新节点返回，因为它是最后一个被访问和更新的节点。

• 步骤10 − 开始main()函数。在main()函数内部，将几个节点插入循环链表中。

• 步骤11 − 现在，调用reverseList()函数，并将第一个非头节点作为当前节点，nil作为前一个节点，头节点作为参数传递给函数。

• 步骤12 − 此外，通过使用fmt.Println()函数在屏幕上打印出反转后的循环链表。

示例

以下是使用递归方法反转循环链表的Go语言程序。

package main

import "fmt"

type Node struct {
   value int
   next  *Node
}

func nodeAdd(head *Node, value int) *Node {
   newNode := &Node{value: value}
   if head == nil {
      newNode.next = newNode
   } else {
      newNode.next = head.next
      head.next = newNode
   }
   return newNode
}

func printList(head *Node) {
   if head == nil {
      fmt.Println("Empty list")
      return
   }
   fmt.Print(head.value)
   current := head.next
   for current != head {
      fmt.Printf(" -> %d", current.value)
      current = current.next
   }
   fmt.Printf(" -> %d\n", head.value)
}

func reverseList(current, prev, head *Node) *Node {
   if current == head {
      current.next = prev
      head.next = prev
      return current
   }
   next := current.next
   current.next = prev
   return reverseList(next, current, head)
}

func main() {
   var head *Node
   head = nodeAdd(head, 5)
   head = nodeAdd(head, 3)
   head = nodeAdd(head, 2)
   head = nodeAdd(head, 4)
   head = nodeAdd(head, 1)

   fmt.Println("Initial linked list:")
   printList(head)
   fmt.Println("Reversed linked list:")
   reversed := reverseList(head.next, nil, head)
   printList(reversed)
}

输出

Initial linked list:
1 -> 5 -> 3 -> 2 -> 4 -> 1
Reversed linked list:
1 -> 4 -> 2 -> 3 -> 5

结论

我们成功地编译和执行了一个使用递归和迭代方法来反转循环链表的 Go 语言程序，同时提供了两个示例。第一个示例中，我们使用了迭代方法；第二个示例中，我们使用了递归方法。反转后的循环链表的结果被输出到控制台。