题解 | #链表中环的入口结点#

集合/哈希

这里用set就可以达到哈希效果，如果有环，那么第一个出现在集合中的重复元素就是环的入口。
（如果使用哈希，发现第一个哈希值为2的就是环的入口）

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode *cur = pHead;
        unordered_set<ListNode*> tmpS;
        while(cur != nullptr){// 没环从这里退出
            if(tmpS.count(cur) > 0){// 如果有环从这里退出
                return cur;
            }
            tmpS.insert(cur);
            cur = cur->next;
        }
        return nullptr;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

双指针法

1. 初始快慢指针，指向链表头节点
2. 快指针每次向后移动两步，满指针每次移动一步（如果链表有环，那么快慢指针一定会相等）
3. 如果快慢指针快慢指针不等且遍历到了尾结点返回null，如果快慢指针相等，那么将快指针移动到链表表头，快指针速度变慢每次移动一步，同时移动两个指针，下次相遇的位置就是环的入口。
   

   class Solution {
   public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
                if(pHead == nullptr)
            return nullptr;
        ListNode *fast = pHead, *slow = pHead;
        while(fast != nullptr && fast->next != nullptr){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)
                break;
        }
        if(slow != fast || fast->next == nullptr)
            return nullptr;
        fast = pHead;
        while(fast != slow){
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    }
   };