c 链表之 快慢指针 查找循环节点(转)
上面分析了 根据这张图
推倒出 数学公式。 刚接触 不能一下弄明白。下面结合上面文章的分析。仔细推倒一下 ,
一般设置 快指针 速度是 慢指针的2倍。及 快指针每次遍历两个指针, 慢指针每次遍历1个指针。
假设上图 快慢指针 在E点相遇,那 相遇点离循环节点D 之间距离是X. 头结点A 离循环节点D 距离为K.
那么在两指针相遇时,各自走过得距离(这里可以吧上图想成是 一个操场,起点不在操场内):
慢指针:
K + X + n*(X+Y) = m;//X+Y 绕环一圈的距离;n 慢指针 总共绕了几圈在环内.
快指针:
试想下 快指针是慢指针 速度的2倍,当它们相遇时 所用的时间是一样的。那么快指针 走过得距离是
2*m;
也等于
K+X +N*(X+Y) = 2*m;//N为快指针绕过得圈数
联立做差上面两公式。
(N-n)*(X+Y) = m; 及
(N-n)*(X+Y) = K+X+n*(X+Y);//这里X+Y 环长是个定值。 假设环长为M
有:(N-n)*M = K+X+n*M;
有:K+X = (N-2*n)*M ;
最终的推倒公式 出来啦。及头节点A 到 循环节点D 的距离 加上 相遇点E离循环节点D 是 环长的整数倍。
这个公式试用于 0 型循环链表 和 6型循环链表。
对于前者 起K 和 X 都为0;快慢指针起点都是循环节点(0型 任意一点都是循环节点)
那么有 (N-2*n)*M = 0;
及 N = 2*n; 相遇时 快慢指针所绕 环的圈数 前者是后者的2倍。 可以想象速度是2呗,所用时间相同。
这里跟环有多少节点没有关系。
上面只是找到了相遇节点。如何找到循环节点。对于6型循环链表。
还是上面推倒公式:
K+X = (N-2*n)*M;//假设N-2*n = Q; 单位为圈数。
有K+X=Q*M; //再假设快慢指针能再循环节点相遇,那么X = 0;
K = Q*M; //Q 的值和K 成正比,这个公式成立条件是 快慢指针相遇 在环上的任意一个点,
假如是E点,结合公式 从E点转Q*M个节点 正好= K 。K的终点正好是循环节点D,及 如果快指针从起点A 走过K 和 慢节点 从E 走过M*Q 相遇节点正好是D循环节点,前提是快慢指针速度相同。
假设将快指针 从头节点开始。慢指针从上次快慢指针相遇点 开始。 两者已相同速度移动。
当快指针走的D 循环节点走过距离为K,慢指针 走到D 循环节点走过的距离为Q*M;
此时 二者相遇 节点就是循环节点。
分析下代码:
Node* findBeginning(Node *pHead)
{
if (NULL == pHead)
return NULL; Node *fast = pHead;
Node *slow = pHead; /*判断是否存在环*/
while (fast->pnext != NULL) //两种情况会跳出循环
{
fast = fast->pnext->pnext;
slow = slow->pnext; if (NULL == fast)
return NULL;
if (fast == slow)
break;
} if (NULL == fast->pnext) //判断是哪种情况导致跳出循环
return NULL; /*查找环起点*/
fast = pHead;
while (fast != slow)
{
fast = fast->pnext;
slow = slow->pnext;
} return fast;
}
关于快慢指针算法:
不仅限于 循环链表问题。
比如查找一个 未知长度链表中中心节点
可以先遍历长度,在遍历到长度/2处返回节点。显然这样 算法不够优化,
使用快慢指针 遍历。快指针速度为 慢得 2倍。
快指针遍历完,返回的慢指针 正好是 长度/2 的节点。
转自:http://www.cnblogs.com/tangbinblog/p/4125842.html
最新文章
- Java 接口练习题
- linux配置网卡绑定
- SQL Server 2014 BI新特性(二)结合Data Explorer和GeoFlow进行数据分析
- windows7 中开启无线热点
- 如何查看Oracle的用户权限
- VS2010 常见错误总结
- java缓存算法【转】
- Keys of HashMap in Java
- UITabBar-UITabBarItem图片的背景颜色属性和文字的颜色大小设置
- linux内核之链表操作解析
- HRBUST 1909 理工门外的树(双数组实现线段树功能)
- linux_操作系统
- Beta阶段敏捷冲刺报告-DAY1
- rman checksyntax和解决RMAN-01009: syntax error: found ";dot";
- 微信订阅号,获取用户openid
- L老师 Shader编程教程 学习
- [UE4]使用UnrealVS扩展快速编译C++代码
- (转)失败和拒绝,也是一种肯定 找工作时,我四处碰壁这一段经历对自己职业生涯的帮助最大。为什么? ";因为这些挫折让我的脸皮变厚了 如果你不是每天被人拒绝,那就说明你的人生目标不够远大 所谓成功,就是不停地经历失败,并且始终保持热情
- PHP中private和public还有protected的区别
- Dubbo问题处理集合
热门文章
- Django初学及mvt模型理解
- Scrapy爬取多层级网页内容的方式
- Pandas中loc,iloc与直接切片的区别
- (转)automaticallyAdjustsScrollViewInsets(个人认为iOS7中略坑爹的属性)
- 【Luogu】P1948电话线(二分SPFA)
- POJ 3693 Maximum repetition substring ——后缀数组
- BZOJ3572 [Hnoi2014]世界树 【虚树 + 树形dp】
- essential c++ 随笔
- SHoj 420 购买装备
- vue之组件理解(一)