描述

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

数据范围： n\le10000 n ≤10000，1<=结点值<=100001<=结点值<=10000

要求：空间复杂度 O(1) O (1)，时间复杂度 O(n) O ( n )

例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：

可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。

输入描述：

输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表

返回值描述：

返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。

示例1

输入：{1,2},{3,4,5}

返回值：3

说明：返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3

示例2

输入：{1},{}

返回值："null"

说明：没有环，返回对应编程语言的空结点，后台程序会打印"null"

示例3

输入：{},{2}

返回值：2

说明：环的部分只有一个结点，所以返回该环形链表入口结点，后台程序打印该结点对应的结点值，即2

第一种方法

简单粗暴，直接循环遍历当前列表，并且把每一个遍历的节点都存起来，如果在遍历的过程中，已经存起来的节点再次出现，则说明出现环，代码实现如下

public ListNode  firstEntryNodeOfLoop(ListNode head){
        HashSet<ListNode> listNodes = new HashSet<>();
        while(head != null){
            if(listNodes.contains(head)){
                return head;
            }else{
                listNodes.add(head);
                head = head.next;
            }
        }
        return null;
    }

第二种方式

指定两个指针，一个慢指针，每次移动一个节点；一个快节点，每次移动两个节点；如果链表没有环，两个指针肯定是不会相遇的，若链表存在环，两个指针必定在某个时间点会相遇，但是这个时候只能证明存在环，并不能说相遇点就是环的入口结点，此时一个从相遇点走，一个从开头走，必会相遇，相遇点则是入口点 但是避免两个是因为null 而相等，代码实现如下

 public ListNode secondEntryNodeOfLoop(ListNode pHead) {
        ListNode quickHead = pHead;
        ListNode slowHead = pHead;
        while(quickHead != null && slowHead != null){
            if(quickHead.next == null){
                return null;
            }
            quickHead = quickHead.next.next;
            slowHead = slowHead.next;
            //说明存在环
            if(quickHead == slowHead ){
                break;
            }
        }
        quickHead = pHead;
        ///一个从相遇点走，一个从开头走，必会相遇，相遇点则是入口点 但是避免两个是因为null 而相等
        while (true){
            if(quickHead == null || slowHead == null){
                return null;
            }
            if(quickHead == slowHead){
                return quickHead;
            }
            quickHead = quickHead.next;
            slowHead = slowHead.next;
        }
    }