Leetcode-142：环形链表II

题目描述：
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

思路：

设置快慢指针slow和fast，slow每次走一步，fast每次走两步。找到第一个相遇点。然后将fast指向链表头，并且步长调整为每次走一步，则下次相遇点即为环入口。

证明： 设环的长度为 t , 链表头到环入口距离为 L1 ， 入口到相遇点的距离为L2，相遇点再走到环入口的距离为L3。 则L1+L2 = t

2（L1+L2 ）= L1 + L2 + k* (L2+L3)
其中k是自然数。表示相遇之前快指针可能走过很多圈环
则L1 = （k-1）L2 + kL3
L1 = (k-1)L2 + (k-1)L3 + L3
L1 = (k-1)(L2+L3) + L3

所以将fast指针从头结点开始走，每次走一步。下次和slow相遇时，slow节点走过了(k-1)圈环以及L3的长度。 而从第一次相遇点开始+L3的长度正好到了环入口。得证。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        
        ListNode slow = head;
        ListNode fast = head;
        
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast)
                break;
        }
        
        if(fast!=null && fast.next!=null){
            fast = head;
            while(fast!=slow){
                fast=fast.next;
                slow=slow.next;
                
            }
            return slow;
        }
        
        return null;
    }
}