题解 | #链表中环的入口结点#
链表中环的入口结点
http://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4
这道题我看了大部分题解,没有比我的简单,虽然牺牲了一点空间复杂度。
用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; } };