教育网站模板下载网站建设 运营

第一种解法时哈希表，set在使用insert插入时，会返回一个pair，如果pair的值为0，则插入失败，那么返回这个插入失败的节点，就是入环的第一个节点，代码如下：

/*** 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) {unordered_set<ListNode*> set;auto cur = head;while(cur != NULL){if(set.insert(cur).second){cur = cur->next;}else{return cur;}}return NULL;}
};

第二种快慢指针的写法，数学推导相当精妙，推到过程可以参考代码随想录-环形链表Ⅱ
参考代码：

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *slow = head, *fast = head;while (fast != nullptr) {slow = slow->next;if (fast->next == nullptr) {return nullptr;}fast = fast->next->next;if (fast == slow) {ListNode *ptr = head;while (ptr != slow) {ptr = ptr->next;slow = slow->next;}return ptr;}}return nullptr;}
};