LeetCode_142环形链表II

题目
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。

思路
包含141中用到的思想，同样用快慢指针来判断环，在141基础上多了一个就是要寻找入环结点，解决此问题用到了一个新的思想：要寻找入环结点，让fast(快)指针从fast和slow相遇的当前位置出发后移(此时以一个单位进行后移)，同时head也往后移，那么当head与fast相遇的位置就是入环结点
难点
fast刚开始以2个单位后移判断环，寻找入环结点时fast以1个单位后移，head也后移，相遇时就是入环结点
图解

代码实现

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null||head.next==null)
            return null;
        ListNode fast=head; //快指针
        ListNode slow=head; //慢指针
        while(fast!=null&&fast.next!=null){ //判断有环
            fast=fast.next.next;    
            slow=slow.next;
            if(fast==slow){ 
               break;       //有环退出当前循环
            }
        }
        if(fast==null||fast.next==null){    //对快指针判空
            return null;
        }
        while(head!=fast){  //寻找入环的位置(开始时为快慢指针相遇的位置)
           head=head.next;//头后移
            fast=fast.next;//快指针后移直到相遇跳出循环
        }
         return fast;   //此时快指针和头相遇所指的位置就是入环节点
}
}