【剑指offer】给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。java实现

【剑指offer】给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。java实现

方法一：复制HashMap

public static ListNode EntryNodeOfLoop(ListNode pHead)
    {
        /**
         * 方法一：辅助HashMap
         */
		HashMap<ListNode,Integer> first = new HashMap<>();
		ListNode pListNode = pHead;
		while(pListNode != null){
			if(!first.containsKey(pListNode)){
				first.put(pListNode, 1);
			}
			else{
				return pListNode;
			}
			pListNode = pListNode.next;
		}
		return null;
		}

方法二：快慢指针

public static ListNode EntryNodeOfLoop(ListNode pHead) {
//因为要移动两步,判断这个和下一个，以及下一个
		if(pHead == null || pHead.next == null || pHead.next.next == null){
			return null;
		}
		//快慢指针
		ListNode p1 = pHead;
		ListNode p2 = pHead;
		//循环链表
		while(p1 != null && p1.next != null &&  p1.next.next != null){
			//快指针移动，慢指针移动
			p1 = p1.next.next;
			p2 = p2.next;
			//相遇就是有环
			if(p1 == p2){
				p1 = pHead;
				while(p1 != p2){
					p1 = p1.next;
					p2 = p2.next;
				}
				if(p1 == p2){
					return p1;
				}
			}
			
		}
		//如果有环，快指针从开始的点开始，慢指针从相遇点开始，各自都走一步
		return null;
    }

主函数：

public static void main(String[] args) {
		ListNode listNode = new ListNode(1);
		ListNode pa = listNode;
		ListNode pb;
		listNode.next = new ListNode(2);
		pa = pa.next;
		pa.next = new ListNode(3);
		pb = listNode.next.next;
		pa = pa.next;
		pa.next = new ListNode(4);
		pa = pa.next;
		pa.next = new ListNode(5);
		pa = pa.next;
		pa.next = new ListNode(6);
		pa = pa.next;
		pa.next = pb;
		
		EntryNodeOfLoop(listNode);
		int res = EntryNodeOfLoop(listNode).val;
		System.out.println(res);
	}

快慢指针思路：
设定两个指针，一个慢指针，一个快指针，快指针的速度是慢指针的两倍，如果有环，他们一定会在环中相遇。
（1） 如果这时快指针已经是在环里走了一圈了（这种情况对应于非环指针较短的情况），如下所示：

根据上图，可以得到下面的关系式：

w + n + y = 2 (w + y)
经过化简，可以得到：w = n - y;
这种情况下，我们就可以直接把p2放在pHead（起始点）处，然后让两个指针以同样的速度走，那么，两者下一次就一定在入口节点相遇了。

（2）如果是相遇的时候，p2已经走了很多圈了，思路也是一样的，只是这时的w会更长一点，并且我们可以肯定的是p1肯定不会绕着圈走一圈，即p1只在环上走了y的距离：

w + y + kn = 2 (w + y)
同样，我们可以推到出来， kn - y = w。

然后，这时还是可以将P2放在pHead处，p1在转了n圈之后，也一定会在入口节点和刚刚到来的p2相遇。