[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
/**
 * 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(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
            // 有环，相遇了
            if(slow == fast) break;
        }
        // 如果fast是空，那么代表无环，否则代表有环，并且slow == fast成立
        // 而且，如果while循环条件一开始就没满足，那么代表head是空节点亦或者长度为1
        if(!fast || !fast->next) return NULL;
        // slow == fast ， 有环
        // 让slow回去，fast和slow以同样的速度走，再次相遇就是环的入口结点
        slow = head;
        while(slow != fast){
            slow = slow -> next;
            fast = fast -> next;
        }
        // 再次相遇了
        return slow;
    }
};