题解 | #链表中环的入口结点#
链表中环的入口结点
http://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4
方法一：对于链表中环的入口结点来说有什么特点，如果遍历整个链表，那么第二次出现的节点也就是此入口节点。那么不妨用一个哈希表来记录链表，然后循环链表，每次遍历到某个节点的时候判断是否在哈希表中出现过。如果未出现，那么记录下来，继续循环。如果出现过，那么这就是入口节点，直接返回即可。 代码：
public:
ListNode* EntryNodeOfLoop(ListNode* pHead) {
unordered_map<ListNode*, int> mp;
ListNode* head = pHead;
while(head != nullptr){
if(mp.find(head) == mp.end()){
mp[head] = 1;
head = head->next;
} else {
return head;
}
}
return nullptr;
}
};
方法二：快慢指针，这个还真不好想到。就是利用路程相等的思想，来控制fast指针和low指针走的速度。具体思路就是先让fast指针每次走两步，low指针每次走一步。那么两个指针一定会在环中某个节点相遇，然后相遇后，让fast指针再次指向head节点。然后再fast和low指针每次走一步，两指针再次相遇就是入口节点。整体思路还是比较简单，但是 个人感觉比较坑的地方就是要处理好无环的情况。
查看19道真题和解析
