题目难度：中等

题目描述：

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

• 数据范围： 0n≤10000，1<=结点值<=10000
• 要求：空间复杂度 O(1)，时间复杂度 O(n)

例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示： 可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。

输入描述： 输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表 返回值描述： 返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。

示例1: 输入：{1,2},{3,4,5} 返回值：3 说明：返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即 3

思路1:快慢指针（推荐）

时间复杂度：O(n)，空间复杂度：O(1) 运行时间：5ms 占用内存：768KB

class Solution {
public:
  	ListNode* EntryNodeOfLoop(ListNode* pHead) {
      	if(!pHead) return nullptr;
      	if(pHead->next = pHead) return pHead;
      
      	ListNode* faster = pHead;
      	ListNode* slower = pHead;
      
      	while(faster) {
          	faster = faster->next->next;
          	slower = slower->next;
          	if(slower == faster) break;
        }
      
      	if(!faster) return nullptr;
      
      	slower = pHead;
      	while(slower != faster) {
          	slower = slower->next;
          	faster = faster->next;
        }
      
      	return slower;
    }
}

思路2:哈希表

时间复杂度：O(n)，空间复杂度：O(n) 运行时间：6ms 占用内存：1164KB

class Solution {
public:
  	ListNode* EntryNodeOfLoop(ListNode* pHead) {
      	if(!pHead) return nullptr;
        if(pHead->next = pHead) return pHead;
      
      	unordered_map<listNode*, int> hash;
      
      	while(pHead) {
          	hash[pHead]++;
          	if(hash[pHead] > 1) break;
          	pHead = pHead->next;
        }
      
      	if(!pHead) return nullptr;
      
      	return pHead;
    }
}

😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘