【力扣】环形链表 II

142. 环形链表 II - 力扣（LeetCode）

题目：

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

思路：

利用快慢指针

代码：

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast && fast->next)
    {
       fast = fast->next->next; 
       slow = slow->next;
       if(slow == fast)
       {
           struct ListNode* temp = head;
           while(1)
           {
               if(temp == slow)
               {
                   return slow;
               }
               temp=temp->next;
               slow=slow->next;
           }
       }
     
    }
    return NULL;
}

拓展：

1、slow一次走1步，fast一次走2步，一定能追上吗？

答：一定可以，假设slow进入循环后与fast的距离为N，fast一次走两步，slow一次走一步，每次fast和slow的距离就会-1，N次后，fast和slow的距离就为0.

2、slow一次走1步，fast一次走3步，能追上吗？fast一次走4步，n步呢？

答：不一定，假设slow进入循环后与fast的距离为N，每一次fast和slow的距离都会-2，如果N不是二的倍数话，fast和slow的距离就不可能为0.

3、证明上述求循环入口的方法。

设进入循环前的那一段距离为 l

入口到fast和slow相遇点的距离为 x

一次循环的长度为 c

slow所走的长度： l+x

fast所走的长度： l + nc+x

fast走的长度是slow的2倍

2（l+x） = I+x +nc

l = nc -x  

l = (n-1)*c + c-x

所以l = c-x

4、其他解决方法

 当fast 和slow相遇后，将循环断开，就变成了求两个链表交点的问题