单链表的成环问题

       前言：链表成环问题不仅考察双指针的用法，该问题还需要一定的数学推理和分析能力，看似简单的题目实则细思缜密，值得斟酌~

目录

1.问题背景引入-判断链表是否成环：

1.1.正解：快慢指针

1.2 STL的集合判重

2.判断入环点问题

2.1.正解：快慢指针

思路分析

代码实现

2.2.相遇点断开判断相交点

思路分析

代码实现

3.金句频道

---

1.问题背景引入-判断链表是否成环：

1.1.正解：快慢指针

对于这个经典问题，一般的，我们得最优解法就是使用快慢指针，下面我们先来分析一下原理：

 

1.2 STL的集合判重

STL还是很好用的，只是会在时间和空间上比双指针算法性能差一些，但胜在思路简单清晰

class Solution {
public:bool hasCycle(ListNode *head) {//快慢指针/*ListNode *slow=head;ListNode *fast=head;bool result=false;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){result=true;break;}}return result;*///C++ STL的setset<ListNode *>mp;ListNode *p=head;while(p){if(!mp.count(p)){mp.insert(p);p=p->next;}elsereturn true;}return false;}
};

2.判断入环点问题

       如果我们需要判断是否成环并在成环前提下找出环的入口节点呢，诸位有什么好方法吗？可以先停下来思考片刻，

 这个题看起来容易，实际上需要用数学归纳法推出可行性的结论进行处理，我们来看。

2.1.正解：快慢指针

思路分析

我们还是用上面所讲的双指针算法，我们这里先给出结论：

  一个指针从相遇点开始走，一个指针从链表头开始走，它们会在环的入口点相遇.

下面我们来做一下推导证明： 

我们来假设下列条件：

根据上图所示，我们来看fast和slow分别走了多少步？

       首先，我们需要知道，fast和slow指针的相遇，会在slow在环内部转了几圈后再追上吗？

这个显然是不可能的，其原因，就是当slow开始进入环时，fast已经在环中的某个点上，此后slow每走一步，fast都会走slow所到节点的两倍，现在变成了fast从slow的背后追slow，并且，slow每走一步，fast都会从它背后追赶两步，造成了两者之间的距离每次缩小1，由于fast在开始追slow是就已经在环中了，所以不用一个环的长度，fast必然追上slow。

        这样一来就好算了，slow走的距离就是L+x，而fast走的距离就是L+C+x，我们可以根据2*slow=fast列出等量关系

                                            2（L+x）=L+C+x；

可以解得：L=C-x，

我知道你急，但是先别急~

如果我的链表是C=1，L=3呢？3=1-（-2）吗？很显然，这不符合逻辑，这是因为我们忽视了一个问题：当L>>C的时候，fast会在环中转很多次才能等到slow进入环中，我们假设这种情况下fast在slow进入环中之前已经转了n次，那么我们的fast走过的实际距离应该为

                                          fast=L+n*C+x；

     此时我们的等式变为：2*（L+x）=L+n*C+x

可以解得

                                        

                                               L=n*C-x；

我们将上面的结论反馈到图中

 进而，我们就可以得出结论，

一个指针从相遇点开始走，一个指针从链表头开始走，它们会在环的入口点相遇.

代码实现

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *slow=head;ListNode *fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){ListNode *meet=slow;//相遇节点//相遇节点和头结点同时走，相遇到的点就是入环节点while(head!=meet){head=head->next;meet=meet->next;}return head;}}return NULL;}
};

2.2.相遇点断开判断相交点

思路分析

       这个思路不难理解，只要我们将相遇点的下一个节点置为NULL，记住相遇点的下一个节点，然后和头结点一起遍历找出地址相同的节点即为入环节点：

代码实现

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *slow=head;ListNode *fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){//相遇节点//cout<<slow->val<<endl;//cout<<fast->val<<endl;ListNode *meetnext=slow->next; //cout<<meetnext->val<<endl;slow->next=NULL;//断开链表，然后开始找两个链表的相交节点//这里我为了方便，直接用STL来判重，写个链表求长度函数，然后将长的链表遍历到和短链表长度一致时再同时开始遍历也可以set<ListNode*> mp;ListNode *p1=head;ListNode *p2=meetnext;//步骤还可以优化while(p1||p2){if(p1&&!mp.count(p1)){mp.insert(p1);p1=p1->next;}else if(p1&&mp.count(p1))return p1;if(p2&&!mp.count(p2)){mp.insert(p2);p2=p2->next;}else if(p2&&mp.count(p2))return p2;}  }}return NULL;}
};

3.金句频道

想什么呢，向前走啊你

      你可以消沉，也可以抱怨，但希望天一亮，你又能顶住四面八方的压力，继续努力的好好生活。不要总抓着过去的事情不放，对那些受过的委屈和伤害耿耿于怀，以及在那些根本无法改变的人和事上面无谓的消耗自己，我们人生的进步就是我们的能力和我们的梦想一次次匹配。