问题

单向链表是否有环 如果有环，找出环的入口

问题阐述

链表在开发过程中属于出现频次十分高的一种数据结构，在java中,比如我们熟知的LinkedList、HashMap底层结构、LinkedHashMap、AQS等都使用到了链表,关于单向链表有几个经典问题 
  1:如何判断链表有环  
  2:如果有环,找出入环的节点
  3:环的长度是多少？本篇博客就围绕这三个问题来展开讨论

问题分析

首先我们来画一个普通的单向链表和环状链表的结构图：

可以看出在环形单向链表的EFGH形成了一个环状,那么如何用程序判断它成环呢？

这里要借助一个跑道的思想：假如有一个环形的跑道，跑道上有两个人P和Q,假设P的速度是1km/10分钟，Q的速度是2km/10分钟,速度恒定不变。如果这个跑道是环型的,他们同时出发,起初Q领先,而在某一个时刻，Q终将从后面追上过P,他们两一定会相遇,而如果是直线跑道,P和Q一定不会相遇。借助于这个思想，我们可以设置快慢指针去绕着环状链表去走，如果两个指针相遇，那么它肯定是环形的。

解决问题

通过设定两个不同速度的快慢指针来遍历整个链表，如果快慢相遇，则整个链表一定有环

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }
        //快慢指针
        // slow 指针一次走一步，fast 一次走两步
        //两个指针相遇的时候，此时表明链表是有环的
        //然后让 fast 指针回到head，变为一次一步走，slow指针维持在原地，保持一次走一步，
        //他们一定会在第一个入环的节点相遇
        ListNode slow = head;
        ListNode fast = head.next;

        while(slow != fast){
            if(fast==null || fast.next ==null){
                return false;
            }

            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
        //循环跳出 表示链表有环
    }
}

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

if(pHead == null) return null;
        // 定义快慢指针
        ListNode slow = pHead;
        ListNode fast = pHead;
        while(fast != null && fast.next != null){
            // 快指针是满指针的两倍速度
            fast = fast.next.next;
            slow = slow.next;
            // 记录快慢指针第一次相遇的结点
            if(slow == fast) break;
        }
        // 若是快指针指向null，则不存在环
        if(fast == null || fast.next == null) return null;
        // 重新指向链表头部
        fast = pHead;
        // 与第一次相遇的结点相同速度出发，相遇结点为入口结点
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;