链表中环的入口结点

Desicription

一个链表中包含环,请找出该链表的环的入口结点。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
private:
unordered_set<ListNode*> book;
public:
ListNode* EntryNodeOfLoop(ListNode* pHead) {
while(pHead != nullptr) {
if(book.find(pHead) == book.end()) {
book.insert(pHead);
pHead = pHead->next;
} else {
return pHead;
}
}
return pHead;
}
};