[AcWing]34. 链表中环的入口结点

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

若其中不包含环，则输出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.

算法思想

y总讲这个题，听得我云里雾里，最终我放弃思考了，直接记住结论，开始写代码。

  1. 慢指针一步一步走，快指针两步两步走
  2. 无环：快指针必定会先到达终点（NULL）
  3. 有环：俩指针会相遇，相遇之后，让慢指针回到起点，再让快慢指针同步速度，一步一步走
  4. 当再次相遇的时候，那个点就是环的入口

代码实现

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
32
33
34
35
36
37
/**
 * 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) {
       ListNode * slow = head, * fast = head;
       
       // 死循环
       while(true){
           // 判断fast -> next是因为fast是连续走两步的
           // 如果fast为空
           // 1. 初始为空
           // 2. 先走完
           if(!fast || !fast -> next) return NULL;
           slow = slow -> next;
           fast = fast -> next -> next;
           // 如果有环，那么这个是唯一的出口
           if(slow == fast) break;
       }
       
       // 跳出循环，必定相遇
       // 快指针从头开始走
       fast = head;
       while(slow != fast){
           slow = slow -> next;
           fast = fast -> next;
       }
       
       return fast;
    }
};