快慢指针
2019年8月24日 星期六, 发表于 深圳
如果你对本文有任何的建议或者疑问, 可以在 这里给我提 Issues, 谢谢! :)
快慢指针，也叫龟兔赛跑算法,Floyd判圈算法，是一个可以在有限状态机、迭代函数或者链表上判断是否存在环，求出该环的起点与长度的算法！
1. 用途
以下参考快慢指针应用总结 https://blog.csdn.net/qq_21815981/article/details/79833976 ，有需要的同学可以跳回原文学习了解；
1.1 判断链表是否有环
主要参考下面的文档：
以下是wiki上的伪代码
1 t := &S
2 h := &S //令指針t和h均指向起點節點S。
3 repeat
4 t := t->next
5 h := h->next
6 if h is not NULL //要注意這一判斷一般不能省略
7 h := h->next
8 until t = h or h = NULL
9 if h != NULL //如果存在環的話
10 n := 0
11 repeat //求環的度
12 t := t->next
13 n := n+1
14 until t = h
15 t := &S //求環的一個起點
16 while t != h
17 t := t->next
18 h := h->next
19 P := *t
1.2 在有序链表中寻找中位数
原理相对简单，直接跳转到 https://blog.csdn.net/qq_21815981/article/details/79833976 阅读即可；