[剑指offer刷题] AcWing 34. 链表中环的入口结点 （双指针、快慢指针）

题型：双指针（快慢指针）

如图所示，

1. 当快指针和慢指针第一次相遇时（假设在c点相遇），我们让慢指针退回到b点，即往回退y距离；此时快指针退回的距离是2y。
2. 此时慢指针刚好走到b点时，快指针走到c’点，c’点与c点关于b点对称，c’b = y， ac’ = 2x。可以得到，圈的长度为x + y。
3. 知道了圈的长度为 x + y 。那么只需要在慢指针走到圈的起点时，让快指针再向前走x距离，即能到达圈的起点。
4. 可以得出结论，在快慢指针第一次相遇时。让慢指针再次回到起点，重新开始走，当快慢指针再次相遇时，此时相遇的点即为圈的起点。

题目

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

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

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

则输出环的入口节点3.

数据范围

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

java代码

/**
 * Definition for singly-linked list.
 * class 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 != null && slow != null) {
            slow = slow.next;
            fast = fast.next;
            
            if (fast != null) {
                fast = fast.next;
                if (fast == null)
                    return null;
            }
            
            if (slow == fast) {
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    if (fast == null)   // 这里确实需要判断一下，因为前面的操作可能让fast为空
                        return null;
                    fast = fast.next;
                }
                
                return slow;
            }
        }
        
        return null;
    }
}