题目描述

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

算法

(快慢指针) $O(n)$

1. 定义一快一慢两个指针。慢指针一次走一步，快指针一次走两步。两个指针同时向前走，如果两个指针能相遇，则环存在。如果快指针走到下一个节点是null，则环不存在。
2. 两个指针能相遇，相遇地点一定是在环里。此时，一个指针停下来，另一个指针每次向前走一步，再次相遇时，走过的长度就是环的周长。
3. 两个指针同时指向起点，一个指针先向前移动环的周长，然后两个指针同时每次向前移动一步，再次相遇时，就是环的入口。

参考文献

【剑指offer】

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) {
        if(head==null || head.next==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        int ringLength=1;
        while(fast.next!=null && fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                slow=slow.next;
                while(fast!=slow){
                    slow=slow.next;
                    ringLength++;
                }
                fast=slow=head;
                for(int i=0;i<ringLength;i++){
                    fast=fast.next;
                }
                while(fast!=slow){
                    fast=fast.next;
                    slow=slow.next;
                }
                return fast;
            }
        }
        return null;
    }
}