- hashset
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *entryNodeOfLoop(ListNode *head) {
unordered_set<ListNode*> s;
if (!head || !head->next) return NULL;
auto cur = head;
while(cur) {
if (s.count(cur)) return cur;
else {
s.insert(cur);
cur = cur->next;
}
}
return NULL;
}
};
2.快慢指针
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *entryNodeOfLoop(ListNode *head) {
if (!head || !head->next) return NULL;
auto first = head;
auto second = head;
while (first && second) {
first = first->next;
second = second->next;
if (second) second = second -> next;
else return NULL;
if (first == second) {
// 慢指针回退到头节点
first = head;
while (first != second) {
first = first->next;
second = second->next;
}
return first;
}
}
return NULL;
}
};