求单链表中环的起点，原理详解

1. 问题描述：

链表结构如下，若链表中有环，返回环的起点，否则返回NULL

1 struct ListNode
2 {
3     int val;
4     ListNode *next;
5     ListNode(const int val):val(val),next(NULL) {}
6 };

 2. 解题代码：

参考 LeetCode

 1 ListNode *detectCycle2(ListNode *head) {
 2     if(!head) return head;
 3     ListNode *stepA = head;// 每次走一步
 4     ListNode *stepB = head;// 每次走两步
 5     while (stepB && stepB->next) {
 6         stepA = stepA->next;
 7         stepB = stepB->next->next;
 8         if(stepA==stepB){
 9             ListNode *stepC = head;
10             while (stepC != stepA) {
11                 stepC = stepC->next;
12                 stepA = stepA->next;
13             }
14             return stepC;
15         }
16     }
17     return NULL;
18 }

3. 原理详解：

（1）假设链表头到环起点的距离为S1，环的长度为S0；在环中相遇时stepA走的路程是SA，stepB走的路程是SB。则当SB>=SA>=S1时，以下结论成立：

(SA-S1) mod S0 = (SB-S1) mod S0    <=>   (SB-SA) mod S0 = 0   <=>   SB-SA = n*S0   <=>   SA=n*S0；  (SB>=SA>=S1)

a. 因为stepB的速度是stepA速度的两倍，所以SB=2SA；

b. 所以 SB-SA=SA=nS0>=S1;

c. 所以 n>=S1/S0，n为自然数

d. 结论：只要满足条件 n>=S1/S0，则stepA和stepB就会在环上相遇；

e. 第一次相遇时 n 的值为 S1/S0 向上取整，假设此时 n=n1，则 SA=n1*S0

（2）stepA和stepB第一次在环上相遇后，让stepB停下，stepC从表头开始走，stepA从当前位置走，并且stepA和stepC一次只走一步。

 假设在环上相遇时stepA走的路程是SAA，stepC走的路程是SC，则当SC>=S1时，以下结论成立：

(SC-S1) mod S0 = (SAA-S1) mod S0    <=>   (SAA-SC) mod S0 = 0     <=>   (SC+n1*S0-SC) mod S0 = 0     <=>   (n1*S0) mod S0 = 0;  (SC>=S1)

a. 因为stepA和stepC的速度相同，所以等式SA A= SC+n1*S0成立；

b. 所以(SAA-SC) mod S0 = 0     <=>   (SC+n1*S0-SC) mod S0 = 0     <=>   (n1*S0) mod S0 = 0

c. 因为 (n1*S0) mod S0 = 0 恒成立，所以 stepA和stepC在环上相遇也恒成立，只要满足SC>=S1就行；

d. stepA和stepC在环上第一次相遇时，SC=S1，此时stepC正好在环的起点。