142.环形链表II

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

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

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

思路

判断链表是否有环

​ 可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。

​ fast 走两个节点，slow走一个节点，有环的话，一定会在环内相遇，而不是永远的错开。因为fast是一个节点一个节点的追赶slow的，因此不会错开的。

​ 因此，fast指针一定先进入环中，如果fast指针和slow指针相遇的话，一定是在环中相遇。

如果有环，如何找到这个环的入口

相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A。

因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：

1
(x + y) * 2 = x + y + n (y + z)

两边消掉一个（x+y）: x + y = n (y + z)

因为要找环形的入口，那么要求的是x，因为x表示 头结点到 环形入口节点的的距离。

所以要求x ，将x单独放在左面：x = n (y + z) - y ,

再从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。

而相遇时候，快指针走了几圈这并不让我关心，我关心的是环形的入口处在哪。假设n=1时候，此时x=z，就是说，当两个指针相遇的时候，再走x步就到环的入口点了。这个x是什么呢？这个x是从链表头走到环形入口的距离。

就是说，(n - 1) (y + z)其实就说fast指针多转的圈数，也是让我不关心的。

c语言实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    typedef struct ListNode ListNode;
    ListNode* fast = head;
    ListNode* low = head;
    while(fast && fast->next){
        fast = fast->next->next;//fast一次走两步
        low = low->next;//low一次走一步
        if(fast == low){//两个环相遇
            fast = head;
            while(fast != low){//到入环口出退出
                fast = fast->next;//此时fast从头开始走，一次走一步
                low = low->next;//从相遇点往前走。一次走一步
            }
            return fast;
        }
    }
    return NULL;
}