链表中环的入口结点

题目来自acwing

题目（点击跳转）

给定一个链表，若其中包含环，则输出环的入口节点。

若其中不包含环，则输出null。

数据范围

节点 val 值取值范围 [1,1000]。

节点 val 值各不相同。

链表长度 [0,500]。

样例

QQ截图20181202023846.png

1
2
3
4
5
6
给定如上所示的链表：
[1, 2, 3, 4, 5, 6]
2
注意，这里的2表示编号是2的节点，节点编号从0开始。所以编号是2的节点就是val等于3的节点。

则输出环的入口节点3.

思路：

双指针实现，定义两个指针，first和second，同时从链表头部开始走，first每次走一步，second每次走两步，当second遇到NULL时代表链表走到尽头，即没有环。当两个指针第一次相遇时，将first重置为头节点的位置，second位置不变，这时让两个指针都已每次一步的距离开始走，当两个指针再次相遇时，这个点就是环的入口。

证明：假设b点为环的起点，当first和second从a开始出发，当first走到b时，first走了距离x，second走过了first两倍的路程，即为2x，second可能在环上已经走过一圈以上，这次加入first再走y距离与second相遇，那么second走的距离即为2y，也就是说当first在b时，second与b的距离为y，那当second走出了b点距离为y时，在环上再走距离x必定可以回到b点，那么将first从头节点开始走x，此时与second第二次相遇即为环的开始节点。

代码：

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
26
27
28
29
30
31
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        if(!head || !head->next) return NULL;
        auto first = head, second = head;
        
        while(first && second) {
            first = first->next;
            second = second->next;
            if(second) second = second->next;
            else return NULL;
            if(first == second){
                first = head;
                while(first != second){
                    first = first->next;
                    second = second->next;
                }
                return first;
            }
        }
        return NULL;
    }
};