- 首页 > it技术 > >
【数据结构|利用快慢指针求链表的中值】思想：慢指针slow遍历链表，faster指针速度是slow的两倍，则当快指针到达链表结尾时（next节点为空），此时slow指针应该位于链表的中间（链表元素个数是奇数时正中间，偶数应该是一半加1）。
package mainimport (
"math/rand"
"time"
"fmt"
)func main() {
p:=Initlist(10)
Traverse(p)
data,index:=Middle(p)
fmt.Printf("中值:%d,位置在%d",data,index)
}
//节点定义
type pnode struct {
data int
next *pnode
}
//初始化长度为n的链表
func Initlist(n int)*pnode{
rand.Seed(time.Now().UnixNano())
pFirst:=&pnode{data:rand.Intn(2n)}
pLast:=&pnode{data:rand.Intn(2n)}
pFirst.next=pLast
for i:=0;
i
性能表现： 时间复杂度：O(n) 空间复杂度：O(1)
推荐阅读
