如何判断链表有环并计算环的长度

原文：http://blog.csdn.net/sdujava2011/article/details/39738313

总体思路:

给出题目：检测单链表中是否存在环。

可以遍历这个链表，遍历过的节点标记为Done，如果当目前准备遍历的节点为Done的时候，那么存在环，否则准备检测的节点为Null时，遍历完成，不存在环。

附加条件：每个节点是只读的，不可以做标记呢？

可以另外开辟一个数组，每次遍历完一个节点后，保存这个节点的唯一地址到数组，如果要遍历的节点已在数组中，那么存在环，要是取到Null还没有重复，那么就是不存在了，当然这个数组可以是Hash表。

附加条件：只可以另外开辟常数空间呢？

可以使用快慢指针，然后分别每次A指针向后移动1步，B指针向后移动2步，如果A和B指向了同一个节点那么存在环，如果有一个指向了Null,那么不存在环。

附件条件：这个环可以出现在任何地方呢？

不可能，只会在最后！

具体方法：

链表球环路的问题经常出现在面试题中，希望通过下面的解释能偶掌握这几个问题。
问题：
1、如何判断一个链表是不是这类链表？
2、如果链表为存在环，如何算环的长度？
3、如果链表为存在环，如何算柄的长度？

第一问是否有环就用快慢指针，fast=fast->next-next,slow=slow->next;代码如下

bool IsExitsLoop(slist *head)
{
    slist *slow = head, *fast = head;

    while ( fast && fast->next )
    {
        slow = slow->next;
        fast = fast->next->next;
        if ( slow == fast ) break;
    }

    return !(fast == NULL || fast->next == NULL);
}

另一种快慢指针的代码写法：（上面的代码更简洁，但下面的代码我感觉更容易理解）

int is_cycle_list(Node *list) {
    Node *one_step, *two_step;
    one_step = two_step = list;
    if(!list) {
         return FALSE;
    }

    while(two_step) {
         one_step = one_step->next;
         two_step = two_step->next;
         if(!two_step) {
              return FALSE;
         }
         two_step = two_step->next;
         if(one_step == two_step) {
              return TRUE;
         }
    }
    return FALSE;
}

int is_cycle_list(Node *list) {
    Node *one_step, *two_step;
    one_step = two_step = list;
    if(!list) {
         return FALSE;
    }
    
    while(two_step) {
         one_step = one_step->next;
         two_step = two_step->next;
         if(!two_step) {
              return FALSE;
         }
         two_step = two_step->next;
         if(one_step == two_step) {
              return TRUE;
         }
    }
    return FALSE;
}

这样就可以判断是否有环路

判断是否有环的第二种方法：反转链表

       反转链表，反转时，会用到3个指针，分别为指向遍历时当前的结点的current指针，指向反转后的子链表的头结点的指针temp，及指向遍历时当前结点的下一个结点的next指针，如果在反转时，出现了next指向头结点的情况，那么肯定是有环的。 
如：1->2->3->4->5->3，反转时，会有以下步骤： 

①temp = NULL; current = 1;  next = 2;  此时，反转生成的子链表：1->NULL 

②temp = 1;  current = 2;  next = 3;  此时，反转生成的子链表：2->1->NULL 

③temp = 2;  current = 3;  next = 4;  此时，反转生成的子链表：3->2->1->NULL 

④temp = 3;  current = 4;  next = 2;  此时，反转生成的子链表：4->3->2->1->NULL 

⑤temp = 4;  current = 5;  next = 3;  此时，反转生成的子链表：5->4->3->2->1->NULL 

⑥temp = 5;  current = 3;  next = 2;  此时，反转生成的子链表：3->5->4->3 断开了 2->1->NULL 
⑦temp = 3;  current = 2;  next = 1;  此时，反转生成的子链表：2->3->5->4->3 断开了 1->NULL 
⑧判断到了next指向了头结点，说明有环。 

代码为： 

int is_cycle_list(Node* head) {
    Node *temp, *current, *next;
    if(!head)
         return FALSE;

    temp = NULL;
    current = head;
    next = head->next;
    current->next = temp;

    while(next) {
         if(next == head) {
              return TRUE;
         }
         temp = current;
         current = next;
         next = next->next;
         current->next = temp;
    }

    return FALSE;
}

第二问

首先引入一个图，

    链表存在环，则fast和slow两指针必然会在slow对链表完成一次遍历之前相遇，证明如下：

slow首次在A点进入环路时，fast一定在环中的B点某处。设此时slow距链表头head长为x，B点距A点长度为y，环周长为s。因为fast和slow的步差为1，每次追上1个单位长度，所以slow前行距离为y的时候，恰好会被fast在M点追上。因为y

    

    fast和slow相遇了，可以肯定的是这两个指针肯定是在环上相遇的。此时，还是继续一快一慢，根据上面得到的规律，经过环长s，这两个指针第二次相遇。这样，我们可以得到环中一共有多少个节点，即为环的长度。

    简言之：第一次相遇后，继续按照2 1的步数走，再次相遇时，slot走的步数为环的长度。

第三问，求柄的长度：

    有人对fast和slow的步长作了不同的设置来改善算法的效率，其实采用别的步长有可能使两指针无法在完成第一次遍历之前相遇，因此步长1和2是一个最优的选择。

假设slow行进了x并在A点进入环路时，fast在环中已经行进了n圈来到B点(n>=0)，其行进距离为2x，则可得到如下等式：2x = x +ns+s-y，做一下运算，即x=(n+1)s-y

若此时再设置一个指向头节点的指针p，而slow在M处，当p行进了x来到A点时，M行进了x=(n+1)s-y，恰好也来到A处，此时，2个指针相遇了。走的步数即为x长度可知。

    简言之：第二次相遇后，fast指针指向head ，按照步长1走，slow指针继续走，知道fast==slow的时候，走的步数就为柄长度x的长度。

算法如下：

slist* FindLoopPort(slist *head,int & cir_length,int & bing_length)
{
    slist *slow = head, *fast = head;

    while ( fast && fast->next )
    {
        slow = slow->next;
        fast = fast->next->next;
        if ( slow == fast ) break;    //判断有环

    }

    if (fast == NULL || fast->next == NULL)//判断有环
        return NULL;
    cir_length = 0;     //环长度
   while ( fast ！= slow )
    {
        slow = slow->next;
        fast = fast->next->next;
    length ++;
    }bing_length = 0;       //环长度
    fast = head;
    while (slow != fast)    //再次相遇
    {
         slow = slow->next;
         fast = fast->next;
    bing_length ++;
     }
     return slow;
}

经过这些代码后，希望能对链表求环的问题有一个更深入的了解。

参考：

http://kb.cnblogs.com/page/52054/

http://www.cnblogs.com/shawn-zhou/archive/2008/11/26/1341307.html

http://kb.cnblogs.com/page/52054/

本文整理自http://blog.csdn.net/guoqiangma/article/details/6933765，http://www.cnblogs.com/yakov/archive/2011/12/17/2291202.html，http://songkang666.iteye.com/blog/1691740，所有权力归原作者所有。