算法1 无脑遍历
用一个unordered_map 存放指针,第一个重复出现的结点就是链表中环的入口结点。
时间复杂度
O(n)
参考文献
C++ 代码
class Solution {
public:
unordered_map<ListNode*,int> hash;
ListNode *entryNodeOfLoop(ListNode *head) {
ListNode* p = head;
while(p){
if (hash[p])
return p;
else if (!hash[p])
hash[p]++;
p = p -> next;
}
return nullptr;
}
};