AcWing 34. 链表中环的入口结点

习题地址 https://www.acwing.com/problem/content/description/86/

题目描述
给定一个链表，若其中包含环，则输出环的入口节点。

若其中不包含环，则输出null。

样例

给定的链表：
[1, 2, 3, 4, 5, 6]
2
注意，这里的2表示编号是2的节点，节点编号从0开始。所以编号是2的节点就是val等于3的节点。

则输出环的入口节点3.

算法1
除开各种技巧解答 本文采取比较中规中矩的解法
开启一个SET记录找到的节点 方便查找

然后遍历链表进行比对 找到相同的节点就说明是环。没有则返回NULL

C++ 代码

/**
 * 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) {
        set<ListNode*> ss;    
        ListNode* p = head;
        while(p != NULL){
            if(ss.count(p) != 0)
                return p;
            ss.insert(p);
            p = p->next;
        }

        return NULL;
    }
};


作者：defddr
链接：https://www.acwing.com/solution/acwing/content/2998/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。