这道题我看了大部分题解,没有比我的简单,虽然牺牲了一点空间复杂度。
用vector或者queue存储你遍历过的结点,每次push遍历判断 当前的下一个指向是否存在相同。
ps:环的入口结点,就是被指向两次的那个结点,这是判断的依据。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead) {
vector<ListNode *> v;//用vector 存储遍历的每个结点
while(pHead!=NULL){
v.push_back(pHead);
for(int i=0;i<v.size();i++){//用当前结点的下一个,与当前存储的结点对比
if(pHead->next == v[i]){
return v[i];
}
}
pHead = pHead->next;
}
return NULL;
}
}; 
京公网安备 11010502036488号