链表中环的入口结点

题意：

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

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

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

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

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

输入描述：

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

返回值描述：

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

示例：

输入：

{1,2},{3,4,5}

返回值：

3

说明：

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

题解：

解法一：快慢指针，使用fast,last两个指针，fast速度为2，last速度为1，当两个指针相遇就说明有环，同时首节点到入口节点等于相遇节点到入口节点，让fast指向首节点，last指向相遇节点，同时往后走，两者相等说明为入口节点

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
 
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        
         ListNode fast=pHead,last=pHead;
        boolean f=false;
        while(fast!=null&&fast.next!=null)
            
        {
            fast=fast.next.next;
            last=last.next;
            if(fast==last)
            {
                f=true;
                
                break;
            }
        }
        if(f)
        {
            fast=pHead;
            while(fast!=last)
            {
                fast=fast.next;
                last=last.next;
            }
            return last;
        }
        return null;
    
    }
}

解法二，将节点装进集合，当集合和中有重复元素则为入口节点