LeetCode 142题解 | 环形链表Ⅱ

一、题目链接

142.环形链表Ⅱ

二、题目

三、分析

返回结点的指针，而不是结点的值。因为结点的值可能会有重复的，但是每一个结点的地址都是独一无二的。

迭代器里面可能存储的是结点的指针。

思路：

1. 若cur不在，就插入到set里。
2. 若cur在，就是带环链表并且cur所在位置就是入口结点。

四、代码编写

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {set<ListNode*> s;ListNode* cur = head;while (cur){auto it = s.find(cur);if (it == s.end()){s.insert(cur);}else{return *it;}cur = cur->next;}return nullptr;}
};