一:题目
二:思路
1.双指针 快慢指针(快指针一次一个结点，慢指针一次两个结点)
2.如果有环的话，那么快慢指针肯定会相遇
3.那么相遇的地点一定在环中 因为如果没有环的话慢指针是永远追不到快指针的
4.接下来就是判断出口在那里，我们定义一个结点从头开始，还有一个结点是从fast结点开始 他俩相遇就是出口点（这个是推导出来的）
三:上码
1:暴力（非上方思路）
/**
* 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){
if(s.count(cur))//这个s.count()函数是判断该值是否存在(因为我们输入的是指针，所以一旦指针相等那么其后面的元素必相等，也就是出现了循环)
return cur;
s.insert(cur);
cur = cur->next;
}
return NULL;
}
};
2:双指针
/**
* 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) {
/**
思路:
1.双指针 快慢指针(快指针一次一个结点，慢指针一次两个结点)
2.如果有环的话，那么快慢指针肯定会相遇
3.那么相遇的地点一定在环中 因为如果没有环的话慢指针是永远追不到快指针的
4.接下来就是判断出口在那里，我们定义一个结点从头开始，还有一个结点是从fast结点开始 他俩相遇就是出口点
*/
ListNode* fast = head;
ListNode* slow = head;
while(fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
//快慢指针相遇
if( slow == fast){
ListNode* temp1 = fast;
ListNode* temp2 = head;
// (快慢指针相等说明 其往后的结点均相等)
while (temp1 != temp2){
temp1 = temp1->next;
temp2 = temp2->next;
}
return temp2;
}
}
return NULL;
}
};
那个推导出口位置解释很长，渣渣杰就直接拿结论来用了 膜拜大佬吧 但是用暴力也是可以解出来的 但是需要用到一个set容器 注意其中 set.count()的用法。最近在听张爱玲的《倾城之恋》其实没听懂 然后今天中午看了改编电影《一炷香》彭于晏太帅了 满满的荷尔蒙 但人物塑造确实在电影中有点渣，电影没啥好看 看弹幕说还是原著好看 还是回归原著吧 听着听着就睡着了 哈哈哈 晚安呐 陌生的你 加油！！！