Golang程序在一次迭代中获得链接列表的中间元素

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

方法1：使用双指针方法

在这种方法中，函数使用两个指针，即低指针和高指针来浏览链表。高指针每次走两步，而低指针则走一步。当高指针到达列表的末端时，低指针将指向链接列表的中间成员。

算法

第1步– 创建一个包main，并在程序中声明fmt(格式包)包，其中main产生可执行代码，fmt帮助格式化输入和输出。
第2步 – 创建一个节点结构，其值为int类型，下一个为节点类型。
第3步 – 创建一个函数middle_node，并在该函数中进一步创建两个指针，low和high，并将它们都设置为指向链表的头部。
第4步 – 直到high到达列表的末尾，遍历链表。
第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步 – 创建一个包main，并在程序中声明fmt(format package)包，其中main产生可执行代码，fmt帮助格式化输入和输出。
第2步 – 创建一个节点结构，其值为int类型，下一个为节点类型。
第3步– 创建一个函数middle_node，并在该函数中初始化一个计数器变量为0和一个指向链表头部的指针节点。
第4步 – 遍历链表，为每个节点增加计数器，并将节点移动到下一个节点，直到节点到达列表的末端。
第5步 – 再次将节点初始化到链表的头部。
第6步 – 迭代计数/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

总结

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

Golang程序在一次迭代中获得链接列表的中间元素

Golang程序在一次迭代中获得链接列表的中间元素

方法1：使用双指针方法

算法

例子

输出

方法2：使用计数器变量

算法

例子

输出

总结

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

Go语言精品教程

回顶部

Golang程序 在一次迭代中获得链接列表的中间元素

方法1：使用双指针方法

算法

例子

输出

方法2：使用计数器变量

算法

例子

输出

总结

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

Go语言 精品教程

回顶部

切换注册登录

用户名或邮箱

密码

切换登录注册

昵称

邮箱

Golang程序在一次迭代中获得链接列表的中间元素

Go语言精品教程