判断链表是否有环

只看该作者 · 2016-12-27 10:42

给定一个单链表，只给出头指针head：
1、如何判断是否存在环？
2、如何知道环的长度？
3、如何找出环的连接点在哪里？
4、带环链表的长度是多少？

解法：
1、对于问题1，使用追赶的方法，设定两个指针slow、fast，从头指针开始，每次分别前进1步、2步。如存在环，则两者相遇；如不存在环，fast遇到NULL退出。
2、对于问题2，记录下问题1的碰撞点p，slow、fast从该点开始，再次碰撞所走过的操作数就是环的长度s。
3、问题3：有定理：碰撞点p到连接点的距离等于头指针到连接点的距离，因此，分别从碰撞点、头指针开始走，相遇的那个点就是连接点。(证明在后面附注)
4、问题3中已经求出连接点距离头指针的长度，加上问题2中求出的环的长度，二者之和就是带环单链表的长度

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) {
      ListNode *p1=head;
      ListNode *p2 = head;
      while (p2 && p2->next) {

      p1 = p1->next;
      p2 = p2->next->next;
      if (p1 == p2)break;
      }
      if (p2==NULL || p2->next == NULL)
         return NULL;
   p1 = head;
   while (p1 != p2){
         p1 = p1->next;
         p2 = p2->next;
   }
   return p1;
}

//判断是否有环
bool isExistLoop(ListNode* head) {

   ListNode *p1=head;
      ListNode *p2 = head;
      while (p2 && p2->next) {

      p1 = p1->next;
      p2 = p2->next->next;
      if (p1 == p2)break;
      }
      return  !(p2==NULL || p2->next == NULL);
}

};

附注
问题2的证明如下：
链表形状类似数字 6 。
假设甩尾（在环外）长度为 a（结点个数），环内长度为 b 。
则总长度（也是总结点数）为 a+b 。
从头开始，0 base 编号。
将第 i 步访问的结点用 S(i) 表示。i = 0, 1 ...
当 i＜a 时，S(i)=i ；
当 i≥a 时，S(i)=a+(i-a)%b 。
分析追赶过程:
两个指针分别前进，假定经过 x 步后，碰撞。则有：S(x)=S(2x)
由环的周期性有：2x=tb+x 。得到 x=tb 。
另，碰撞时，必须在环内，不可能在甩尾段，有 x>=a 。
连接点为从起点走 a 步，即 S(a)。
S(a) = S(tb+a) = S(x+a)。
得到结论：从碰撞点 x 前进 a 步即为连接点。
根据假设易知 S(a-1) 在甩尾段，S(a) 在环上，而 S(x+a) 必然在环上。所以可以发生碰撞。
而，同为前进 a 步，同为连接点，所以必然发生碰撞。
综上，从 x 点和从起点同步前进，第一个碰撞点就是连接点。