数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Go 语言程序：单次迭代获取链表中间元素
在 Go 语言数据结构中，链表使用指针连接各个元素，从第一个节点（头部）到最后一个节点（尾部），可以通过 next 指针访问每个节点。我们将使用两种方法获取链表的中间元素。第一种方法使用双指针法，第二种方法使用计数器变量来执行程序。
方法 1：使用双指针法
在这种方法中，函数使用两个指针 low 和 high 遍历链表。high 指针每次移动两步，而 low 指针每次移动一步。当 high 指针到达链表末尾时，low 指针将指向链表的中间元素。
算法
步骤 1 − 创建一个名为 main 的包，并在程序中声明 fmt（格式化包），其中 main 生成可执行代码，fmt 帮助格式化输入和输出。
步骤 2 − 创建一个节点结构体，其中包含类型为 int 的值和类型为 node 的 next 指针。
步骤 3 − 创建一个名为 middle_node 的函数，并在该函数中进一步创建两个指针 low 和 high，并将它们都设置为指向链表的头部。
步骤 4 − 循环遍历链表，直到 high 指针到达链表末尾。
步骤 5 − 在每次循环中，将 low 指针移动一步，high 指针移动两步。
步骤 6 − 当 high 指针到达链表末尾时，low 指针将指向链表的中间元素。
步骤 7 − 在下一步中，将 low 指针返回到函数。
步骤 8 − 对于具有奇数个元素的链表，当 high 指针到达链表末尾时，low 指针将指向中间元素。对于具有偶数个元素的链表，low 指针将指向两个中间元素中的一个。
示例
在本例中，我们使用了双指针法从链表中获取中间元素。
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 − 创建一个名为 main 的包，并在程序中声明 fmt（格式化包），其中 main 生成可执行代码，fmt 帮助格式化输入和输出。
步骤 2 − 创建一个节点结构体，其中包含类型为 int 的值和类型为 node 的 next 指针。
步骤 3 − 创建一个名为 middle_node 的函数，并在该函数中初始化一个计数器变量为 0，以及一个指向链表头部的节点指针。
步骤 4 − 遍历链表，为每个节点递增计数器，并将节点移动到下一个节点，直到节点到达链表末尾。
步骤 5 − 再次将节点初始化为链表的头部。
步骤 6 − 迭代 count/2 次，每次将节点移动到下一个节点。
步骤 7 − 返回节点，该节点将指向链表的中间元素。
步骤 8 − 使用 fmt.Println() 函数在主函数中打印接收到的节点，其中 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
结论
我们使用两种方法执行了获取链表中间元素的单次迭代程序。在第一种方法中，我们使用了双指针法，在第二个示例中，我们使用了计数器变量来跟踪链表的元素。
211 次浏览
