当前仅显示指定条件回帖 [ 展开查看全部 ]
文件名称:
README.md
所在目录:
教材与参考资料 / 程序设计类 / 数据结构＆算法 / 算法 / 面试与力扣题目详解 / Leetcode题目和解答 / java-leetcode / linked-list-cycle-ii
文件大小:
691.00 B
下载地址:
文本预览:
## More work after [Linked List Cycle I](../linked-list-cycle)
To find where the cycle begins, we can use a fast-slow pointer.
The faster one walks `length of the cycle` steps before the slower one, and then, the slower one start to walk.
Where the faster one and slower one meet is the point that the cycle begins.
## Measure the length of the cycle
After the fast-slow runners encounter, let them go on running until they will meet at some point.
If slow-runner walks `1` step each loop, when they meet again, the slow-runner will walk `length of the cycle` steps.
So, code might be like
```
loop until fast meets slow
if not meet first time
length = length + 1
```
To find where the cycle begins, we can use a fast-slow pointer.
The faster one walks `length of the cycle` steps before the slower one, and then, the slower one start to walk.
Where the faster one and slower one meet is the point that the cycle begins.
## Measure the length of the cycle
After the fast-slow runners encounter, let them go on running until they will meet at some point.
If slow-runner walks `1` step each loop, when they meet again, the slow-runner will walk `length of the cycle` steps.
So, code might be like
```
loop until fast meets slow
if not meet first time
length = length + 1
```
点赞
回复
X