1 /**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 * int val;
5 * ListNode *next;
6 * ListNode(int x) : val(x), next(NULL) {}
7 * };
8 */
9 class Solution {
10 public:
11 ListNode *detectCycle(ListNode *
head) {
12 ListNode* fast=
head;
13 ListNode* slow=
head;
14 while(
1){
15 if(fast==NULL||fast->next==
NULL)
16 return nullptr;
17 fast=fast->next->
next;
18 slow=slow->
next;
19 if(fast==
slow)
20 break;
21 }
22 ListNode* p=
head;
23 while(p!=
slow){
24 p=p->
next;
25 slow=slow->
next;
26 }
27 return slow;
28 }
29 };
先用快慢指针判定是否存在环
令入环前长度为x，环长为c，两个指针在距离入环节点k处相遇，此时快指针走了m次环，慢指针走了n次环
fast=2slow
由上式可以得到
x+m*c+k=2*(x+n*c+k)
m*c=x+k+2*n*c
x+k=v*c 这意味着，x+k必然是环长c的整数倍
再看慢指针，慢指针在环中，距离入环节点k，即已经走过了入环节点k的距离
此时，再将慢指针向后走x步，即慢指针距离入环节点为(x+k)，正好是环长c的整数倍，这意味着，移动后的慢指针必然停在入环节点处
所以，代码中，将头结点指针p向后移动，直到与慢指针slow相遇，因为p走到入环节点正好k步
慢指针走k步可能会走过入环节点，就是可能会在环里绕圈子，不仅仅走了一圈，但是，走完k步，慢指针一定停在入环节点
因此，p指针和slow指针一定会在入环节点处相遇
判定相遇，返回慢指针即可
转载于:https://www.cnblogs.com/zhuangbijingdeboke/p/11317601.html
相关资源：JAVA上百实例源码以及开源项目
