题目描述：

单链表有环指的是单链表中的某个结点的next域指向链表中他之前的某一个结点，这样在链表的尾部形成一个环形结构，如果有环，怎么找出环的入口点。

方法一：蛮力法

定义一个HashSet用来存放结点的引用，从链表的头结点开始向后遍历，每遍历到一个节点就判断HashSet中是否存在这个结点的引用，如果没有说明是第一次访问，还没有形成环，那么将这个结点的引用添加到HashSet中。如果在HashSet中找到了同样的节点，说明这个结点已经被访问过，于是就形成了环。这种方法时间复杂度和空间复杂度都是O(N)

方法二：快慢指针法

定义两个指针fast和slow，两者初始值都是指向链表头，slow每次前进一个结点，fast每次前进两个结点。如果fast在移动过程中等于slow,说明链表有环，否则没有环。当链表有环，那么当指针fast与slow相遇时，slow指针肯定没有遍历完链表，而fast指针已经在环内循环了n圈（n>=1）。如果slow指针走了S步，则fast走了2s（fast步数还等于s+在环上多转的n圈），假设环长为r，则满足

2s=s+nr

由此可得s=nr

设整个链表长为L ,入口环与相遇点距离为x，起点到到环入口距离为a，可得

a+x=nr (slow走的距离)a+x=(n-1)r+r=(n-1)r+L-a (L-a是环的长度)a=(n-1)r+(L-a-x)

(L-a-x)为相遇点到环入口的距离（注意不是环入口到相遇点的距离）。从链表头到环入口点的距离=(n-1)*环长+相遇点到环入口的距离。于是从链表头与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇的第一点位环入口点。

public static Node isLoop(Node head) {        if (head == null || head.next == null) {            return head;        }        Node slow = head.next;        Node fast = head.next;        while (fast != null && fast.next != null) {            slow = slow.next;            fast = fast.next.next;            if (slow == fast) {                return slow;            }        }        return null;    }    public static Node findLoopNode(Node head,Node meetNode) {        Node first = head.next;        Node second = meetNode;        while (first != second) {            first = first.next;            meetNode = meetNode.next;        }        return first;    }    public static Node buildNode() {        int i = 1;        Node head = new Node();        head.next = null;        Node tmp;        Node cur = head;        for (;i<8;i++) {            tmp = new Node();            tmp.value = i;            tmp.next = null;            cur.next = tmp;            cur = tmp;        }        return head;    }    public static void main(String[] args) {        Node head = buildNode();        Node meetNode = isLoop(head);        Node loopNode;        if (meetNode != null) {            System.out.println("有环");            loopNode = findLoopNode(head,meetNode);            System.out.println("环的入口点位:" + loopNode.value);        } else {            System.out.println("无环");        }    }

算法性能分析：

只需要对链表遍历一次，时间复杂度为O(N)，由于只需要几个指针变量来保存结点地址信息，空间复杂度为O(1)。