线性表的链式存储，以及使用快慢指针找不知长度链表的中间节点
题目描述
首先，给定一个带有头结点 head 的不知长度链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。注意链表长度未知，这里测试定义的链表结构体存储的数据类型可以用字符串类型。
示例说明：
实例1
输入：“one”-"two"-"three"-"four"-"five"
输出：链表的中间节点为 ["three"]
实例2
输入：“tom”-"jack"-"kaka"-"James"-"vickor"-"wade"-"aha"-"tiger"
输出：链表的中间节点为 ["James","vickor"]
解题思路
设置两个指针，一个快指针，每次走两步，一个慢指针，每次走一步，当快指针为空(偶数个节点)或者快指针的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
}
}
}
最后，通往北京的路有很多条，你也可以有其他更好的方法，欢迎一起交流学习，共同进步。
有疑问加站长微信联系（非本文作者）
