题解 | #链表中环的入口结点#

链表中环的入口结点

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;
    }
};


全部评论

相关推荐

待现的未见之事:起码第一句要把自己的优势说出来吧。比如什么xx本27届学生,随时到岗....
点赞 评论 收藏
分享
05-24 20:52
东南大学 C++
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务