检查链表内是否有环

国庆，同学来我这里，疯了几天，什么都没学，好有罪恶感，关键是学习有点进入不了状态，看到两个小算法题，找找学习的感觉

一、检查链表中是否有环
题目描述：
    给定一个单链表，判定其中是否有环，即链表的最后一个结点的next指针不是空指针，而是指向了链表中的某一个结点。

思考：
    假设最后一个结点的next指针指向的是头结点，即：1->2->3->4->5->1，整体成环，这种情况比较好解决，只需一个指针指向头结点，另一个指针向后遍历，当两个指针指向同一结点时，可以判定是有环的。
    假设最后一个结点的next指针指向的是除头结点外的某一结点，如：1->2->3->4->5->3，局部成环，这种情况就不能用一个指针指向某一指定的结点，然后遍历，从而判断是否为环，因为这一“某一指定的结点”是不确定的，你不能让一个指针指向2（例子中是2）。
    于是，有了下面的思路。

思路一：
    反转链表，反转时，会用到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;
}

思路二：
    用两个指针one_step，two_step，一块向后遍历，遍历时，one_step每次向后跳一步，two_step每次向后跳两步，直到two_step指向NULL，说明没有环（two_step肯定比one_step先到链表的尾部），或者两个指针都没有遍历到NULL结点，而两指针指向了同一结点，说明two_step赶上了one_step，此时肯定是有环的。

代码为：

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;
}

第一种方法反转了链表，需要再反转回来，才能还原到初始链表

扩展一下，如果判断到一个链表内部是有环的，如何找到从哪个结点开始，形成的环？？？
谁有好方法啊！！！！

评论

1 楼 nonocast 2012-10-07  

用2个pointer差异追逐