LeetCode.142 环形链表II

1.题目：

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

 2.代码

/**
 * 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 fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){//注意这里是快指针和快指针的下一个不为空，不要判断慢指针
            fast = fast.next.next;//快指针一次跳两步
            slow = slow.next;//慢指针一次跳一步
            if(fast==slow){//当快慢指针相遇时就说明是有环的
                ListNode index1 = fast;//定义一个指针指向快指针或慢指针
                ListNode index2 = head;//定义一个指针指向头结点
                while(index1!=index2){//当两个指针相遇时说明是在环形入口相遇的
                    index1 = index1.next;//两个指针分别相遇
                    index2 = index2.next;
                }
                return index2;//返回环形入口
            }
        }
        return null;//走到这里说明没有没有环形返回null
    }
}

2.注意点

1.快慢指针的思路

2.防止空指针异常的判断

3.判断环形入口方法（由数学公式判断）