Golang使用快慢指针找不知长度链表的中间节点 Golang使用快慢指针找不知长度

线性表的链式存储，以及使用快慢指针找不知长度链表的中间节点
题目描述首先，给定一个带有头结点 head 的不知长度链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。注意链表长度未知，这里测试定义的链表结构体存储的数据类型可以用字符串类型。
示例说明：
实例1
输入：“one”-"two"-"three"-"four"-"five"
输出：链表的中间节点为 ["three"]
实例2
输入：“tom”-"jack"-"kaka"-"James"-"vickor"-"wade"-"aha"-"tiger"
输出：链表的中间节点为 ["James","vickor"]
解题思路 【Golang使用快慢指针找不知长度链表的中间节点】设置两个指针，一个快指针，每次走两步，一个慢指针，每次走一步，当快指针为空(偶数个节点)或者快指针的next指针指向空时(奇数个节点)，此时慢指针即为中间节点。
步骤：
首先定义线性表的链式存储，单个节点的定义如下
type Node struct { // 定义一个node结构体
data string
next *Node
}
紧接着定义相应的方法，主要有增加节点Append、获取长度GetLength、获取中间节点GetCenterNode等。
在链表尾部增加节点：
func (n *Node) Append(data string){
createNode := &Node{data,nil}
for n.next != nil{
n = n.next
}
n.next = createNode
}
获取整个链表的长度：
func (n *Node) GetLength() int{
if n.next==nil{
return 0
}
length:= 0
for n.next!=nil{
length ++
n = n.next
}
return length
}
获取整个链表中间节点：（这里有对不同情况分别讨论，如一些边界条件、链表长度为奇数偶数时分别讨论）
func (n Node)GetCenterNode()[]string{
str := make([]string,0,2)
if n.next==nil{
return nil
}
l := n.next
s := n.next
for s.next!= nil{
// 单数情况
if l.next==nil{
str = append(str, s.data)
return str
}
// 双数情况
if l.next != nil && l.next.next == nil{
str = append(str,s.data)
str = append(str,s.next.data)
return str
}
s =s.next
l = l.next.next
}
return str
}
首先初始化一个链表
// 初始化一个链表
func initLinkList ()Node{
return &Node{"genesis node", nil}
}
通过随机数拼接生成一个长度为20的随机链表，用于测试
func Rand20List(n *Node){
for i:=0; i<3; i++{
n.Append("this is "+strconv.Itoa(i))
}
}
通过main函数进行测试，当然也可通过写测试函数进行测试。
func main(){
link := initLinkList()
var s int
for {
fmt.Println("1.查看链表")
fmt.Println("2.创建链表20个数据")
fmt.Println("3.链表长度")
fmt.Println("4.查看中间节点值")
fmt.Println("5.退出")
fmt.Println("请输入选择：")
fmt.Scan(&s)
switch s {
case 1:
fmt.Println(link.MapLinkList())
case 2:
Rand20List(link)
case 3:
fmt.Println(link.GetLength())
case 4:
fmt.Println(link.GetCenterNode())
case 5:
return
}
}
}
完整代码完整线性表的链式存储，以及使用快慢指针找不知长度链表的中间节点代码如下：

package main import ( "fmt" "strconv" ) // 定义一个node结构体 type Node struct { data string next *Node } func (n *Node) Append(data string){ createNode := &Node{data,nil} for n.next != nil{ n = n.next } n.next = createNode } func (n *Node) GetLength() int{ if n.next==nil{ return 0 } length:= 0 for n.next!=nil{ length ++ n = n.next } return length } func (n *Node) MapLinkList()[]string{ var str []string if n.next == nil{ return nil } for n.next != nil{ str = append(str,n.next.data) n = n.next } return str } // 快慢指针法求不知道长度的链表的中间值 func (n *Node)GetCenterNode()[]string{ str := make([]string,0,2) if n.next==nil{ return nil } l := n.next s := n.next for s.next!= nil{ // 单数情况 if l.next==nil{ str = append(str, s.data) return str } // 双数情况 if l.next != nil && l.next.next == nil{ str = append(str,s.data) str = append(str,s.next.data) return str } s =s.next l = l.next.next } return str } // 初始化一个链表 func initLinkList ()*Node{ return &Node{"genesis node", nil} } func Rand20List(n *Node){ for i:=0; i<3; i++{ n.Append("this is "+strconv.Itoa(i)) } } func main(){ link := initLinkList() var s int for { fmt.Println("1.查看链表") fmt.Println("2.创建链表20个数据") fmt.Println("3.链表长度") fmt.Println("4.查看中间节点值") fmt.Println("5.退出") fmt.Println("请输入选择：") fmt.Scan(&s) switch s { case 1: fmt.Println(link.MapLinkList()) case 2: Rand20List(link) case 3: fmt.Println(link.GetLength()) case 4: fmt.Println(link.GetCenterNode()) case 5: return } } }

最后，通往北京的路有很多条，你也可以有其他更好的方法，欢迎一起交流学习，共同进步。