C++解OJ题--环形链表

C++解OJ题--环形链表

  害怕犯错而不去犯错才是最大的错误！
  哈哈，登场的时候先抒情一下！今天又解了一道算法题，一起来看看吧

---

原题如下：

  给定一个链表，判断链表中是否有环。
  如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
  如果链表中存在环，则返回 true 。 否则，返回 false 。

---

审题：

1.给定一个链表，判断是否有环；
2.如果链表有环，则不存在某个结点的next域为NULL的情况；
3.如果链表没有环，则存在最后一个结点的next域为NULL；
4.我们只需要判断有没有环，而对于尾部连接到哪个结点我们不需要进行关心；
5.空间复杂度为O（1）。
  对于题目的描述多多少少有点迷惑人，所以审题特别关键，要认真审题，只有提取了题目的关键信息，才能往下进行。

---

可能给我们的链表情况：

1.一个空链表；
2.没有环的链表；
3.有环的链表。

---

先来记录一下我的分析过程，这对于读者来说可能意义不大，可以略过：

如何判断是否有环？
  对于一个链表中的结点重复访问了两次。
能否用数据来判断对该结点访问了两次？
  不能,因为可能存在结点数据相同的两个结点。
那应该用什么来判断?
  什么是结点特有的？每个结点的地址是特有的，如果对一个结点地址重复访问了两次，则说明存在环，反之如果程序结束了，都没有多次访问同一个地址则说明不存在环。
  通过上面的分析，我们是不是需要开辟一个数组来存每个结点的地址，但是这显然不满足空间复杂度为O（1），那上面的方式必然不可靠。

---

正题：

  上面的三种情况，对于前两种情况我们都很好判断,关键在于第三种情况。如果存在环,我们就不可能像以前一样，判断next域是否为空。然而对于判断的过程我们当然采用循环来遍历,但再不借助额外空间的前提下，如何让一个循环结束？
  其实本题我们的关注点是：我们只需要判断有没有环，而对于尾部连接到哪个结点我们不需要进行关心；

快慢指针登场：
  慢指针走一个结点，而快指针走两个结点。
  如果不存在环，那么快指针的next域为NULL，或者快指针的next的next域为NULL则结束循环，返回false；
  如果存在环，那么快慢指针必然会有重合的时候，即它们都会在同一个结点相遇。相遇的时候则返回true结束循环。
  因为思想比较简单，我就不画图了，来看看代码吧。

---

代码如下：

class Solution {
public:
    bool hasCycle(ListNode *head) {
     if(head==NULL)return false;
     ListNode*fast=head;//快指针
     ListNode*slow=head;//慢指针
     while(fast->next&&fast->next->next)
     {
         slow=slow->next;
         fast=fast->next->next;
         if(slow==fast)return true;
     }
     return false;
    }
};

---

我是“老胡”，感谢阅读！！！