题目

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

思路

1. 快慢指针的是否相遇，判断是否有环
2. 判断环入口
   当slow与fast相遇在环内某个节点，slow走了x个节点，fast走了2x个节点；
   l为整个链表的长度，y为入口到slow的距离，z为head到入口的距离
   2x = l+y
   x = z+y
   所以l-x = z, 也就是说这样新的节点与slow会在环开始的地方相遇

代码

package linkList;

/**
 * Created by liqiushi on 2018/1/12.
 */
public class LinkedListCycleTwo {
    public ListNode detectCycle(ListNode head) {
        if(head == null||head.next == null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
}