Golang 在单次迭代中获取链表的中间元素

在golang数据结构中，链表通过指针连接各个项，从第一个节点（头节点）到最后一个节点，可以使用下一个指针访问每个节点（尾节点）。我们将使用两种方法获取链表的中间元素。第一种方法使用双指针方法，第二种方法使用计数器变量来执行程序。

方法1：使用双指针方法

在这种方法中，函数使用两个指针low和high遍历链表。高指针每次移动两步，低指针每次移动一步。当高指针到达链表末尾时，低指针将指向链表的中间成员。

步骤

• 步骤1 − 在程序中创建一个main包，并声明fmt（格式化包）包，其中main产生可执行代码，fmt用于格式化输入和输出。

• 步骤2 − 创建一个类型为int的值和类型为node的next值的节点结构体。

• 步骤3 − 创建一个middle_node函数，并在该函数中创建两个指针low和high，并将它们都设置为指向链表的头。

• 步骤4 − 在高指针到达链表末尾之前，通过链表进行迭代。

• 步骤5 − 每次循环中，低指针移动一步，高指针移动两步。

• 步骤6 − 当高指针到达链表末尾时，低指针将指向链表的中间成员。

• 步骤7 − 在下一步中，将低指针返回给函数。

• 步骤8 − 这种方法有效是因为当高指针到达链表末尾时，低指针将指向链表中间的元素，对于具有奇数个条目的链表，低指针将指向两个中间元素中的第一个中间元素。

示例

在这个示例中，我们使用了两个指针的方法来获取链表的中间元素。

package main
import "fmt"

type Node struct {
   value int
   next  *Node
}

func middle_node(head *Node) *Node {
   low, high := head, head
   for high != nil && high.next != nil {
      low = low.next
      high = high.next.next
   }
   return low  //the low is pointing to middle element
}

func main() {
   head := &Node{value: 10}  //store values in the linked list
   head.next = &Node{value: 20}
   head.next.next = &Node{value: 30}
   head.next.next.next = &Node{value: 40}
   head.next.next.next.next = &Node{value: 50}

   node := middle_node(head)   //obtain the middle node from the linked list
   fmt.Println("The middle node in the linked list is:", node.value)
}

输出

The middle node in the linked list is: 30

方法2：使用计数器变量

在这种方法中，我们首先计算链表中有多少个元素。然后再通过第二次迭代链表，通过迭代 count/2 次停止在中间节点上。输出将是一个在控制台上使用 fmt 包打印出来的中间节点。

步骤

• 步骤 1： - 创建一个 package main，并在该程序中声明 fmt（格式化包）包，其中 main 生成可执行代码，fmt 用于格式化输入和输出。

• 步骤 2： - 创建一个名为 node 的结构体，其中值的类型为 int，next 的类型为 node。

• 步骤 3： - 创建一个名为 middle_node 的函数，在该函数中将计数器变量初始化为 0，并创建一个指向链表头部的指针。

• 步骤 4： - 迭代链表，对每个节点增加计数器并将节点移动到下一个节点，直到节点到达链表末尾。

• 步骤 5： - 将节点再次初始化为链表的头节点。

• 步骤 6： - 迭代 count/2 次，每次将节点移动到下一个节点。

• 步骤 7： - 返回指向链表中间元素的节点。

• 步骤 8： - 使用 fmt.Println() 函数在 main 函数中打印接收到的节点，其中 ln 表示换行。

示例

在这个示例中，我们将使用计数器变量来找到链表的中间元素。

package main
import "fmt"

type Node struct {
   value int
   next  *Node
}

func middle_node(head *Node) *Node {
   count := 0
   node := head
   for node != nil {
      count++
      node = node.next
   }

   node = head
   for i := 0; i < count/2; i++ {
      node = node.next
   }
   return node //here node points to middle element
}

func main() {
   head := &Node{value: 10}    //fill the linked list with required values
   head.next = &Node{value: 20}
   head.next.next = &Node{value: 30}
   head.next.next.next = &Node{value: 40}
   head.next.next.next.next = &Node{value: 50}

   node := middle_node(head)  //obtain the middle element in the node
   fmt.Println("The middle node in the linked list is:", node.value)
}

输出

The middle node in the linked list is: 30

结论

我们使用两种方法执行了在单次迭代中获取链表中间元素的程序。在第一种方法中，我们使用了两个指针的方法，而在第二个示例中，我们使用计数器变量来跟踪链表元素。