剑指offer-链表中环的入口节点

本文为剑指 offer 系列第五十二篇。
主要知识点为链表的遍历，同样的使用一个set就可以解决问题。

题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

解题思路

思路非常清晰，从头开始遍历，遍历的时候先判断当前节点是否在set中，如果已经在，那么这个节点肯定就是那个入口节点。如果不在，继续向后遍历。

解题代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* head)
    {
        set<ListNode*> mset;
        ListNode* p = head;
        while(p){
            if(mset.count(p)) return p;
            mset.insert(p);
            p = p->next;
        }
        return NULL;
    }
};

时间复杂度为O(n),空间复杂度为O(n)

以上，本题结束！