【问题】给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
【思路】第一种思路最好想，也最容易入手，使用一个hash_set，保存访问过的节点地址，再遍历的同时进行搜索，如果搜到了，直接退出循环，返回这个节点即为入环节点，如果没有环，则遍历到nullptr退出，返回nullptr即可！
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { if(pHead == nullptr || pHead->next == nullptr || pHead->next->next == nullptr){ return nullptr; // 三个节点以下不可能成环 } unordered_set<ListNode*> set; ListNode* cur = pHead; while(cur != nullptr){ if(set.find(cur) == set.end()){ set.insert(cur); }else{ break; } cur = cur->next; } return cur; } };
另外一个思路是快慢指针，可以做到空间复杂度为O(1)，其具体的数学论证过程就不细讲了，我也没有推导过，具体做法是：设置快慢指针，快指针指向慢指针的next，然后快指针一次走两步，慢指针一次走一步，如果有环结构，那么两个指针会一定重合，此时将一个指针指向头部，两个指针同时走，一次走一步，最终会在环的入口处再次相遇！返回当前节点即可
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { if(pHead == nullptr || pHead->next == nullptr || pHead->next->next == nullptr){ return nullptr; // 三个节点以下不可能成环 } ListNode* n1 = pHead->next; ListNode* n2 = pHead->next->next; while(n1 != n2){ if(n2->next == nullptr || n2->next->next == nullptr){ return nullptr; } n2 = n2->next->next; n1 = n1->next; } n2 = pHead; while(n1 != n2){ n1 = n1->next; n2 = n2->next; } return n1; } }
原文：https://www.cnblogs.com/zhudingtop/p/11456032.html