如何判断单向链表有环？

昨天去面试了一把，面试官给出了这道题。当时我知道一定有什么巧妙的办法，但是我并没有想到。我只是想到了通用的方法，顺序遍历然后为遍历过的节点依次做标志。也试图去想了些特殊的访法，不过都有一定的局限性。事后得知了下面这个较优的方案。 typedef struct NodeTag { struct type data; node * next; }Node; 题目：如何判断单项链表有死循环？ 答案：定义两个指针p、q，然后让p、q同时从链表头向后查找，注意他们移动的步幅是不同的分别为a 、b，例如p指针每次执行一次【p = p->next;】q每次执行两次【q = q->next;】，如果q先到链尾【if(q->next == NULL)】则没有死循环（这里假设q比p的移动速度要快），如果p、q在此之前相遇了则有死环。

对于这个答案少不了的还是欣赏，这确实是个good idea.但是返回来一想，会不会有这样的情况，p与q永远不会相遇呢？这里就涉及到a和b应该如何选择的问题，它们的设置必须要保证如果链表上有死环，p、q一定会在有限的步数内相遇。网上有人说a，b的只要是素数就行，有人说a、b大一点好，但a、b的值到底应该如何选择呢？ 分析：假设链表上有环的情况，按照前面说的方案经过了多次移动以后p和q都会上环，上环后其实就是一个追逐问题，如果a<b,且a和b距离是h，环长c。设迭代了x次后p和q相遇且相遇时q比p多跑y圈，可得出方程【ax+yc=bx+h】和【b>a】；即【x=(cy-h)/(b-a)】，注意这里的x一定要是正整数。由于c和h都是随机数，所以【(cy-h)】的结果可以是任何一个正整数。问题转变成了a和b必须满足任意整数都可以除尽【(b-a)】，这下好了终于可以得出答案：因为任意整数除以1都等于它本身。这里只要满足条件【b-a=1】 即可。也就是说p和q的步幅只要相差1就可以保证在有限次迭代后可以找出链表上的环。

问题1. 一个单向链表，请设计判断该链表中有没有环？

思路1：声明一个指向链首的指针和一个足够大的int数组(或hash表，用于保存地址)，逐个节点地遍历链表；遍历过程中，先判断该节点的地址是否已经在数组中存在了，如果不存在，则将该地址加入数组并让指针指向下一个节点；如果存在，则证明链表中有环。这种方法需要用数组来保存地址，并反复遍历该数组，效率很低，伪代码如下： 1Node * ptr = head;//链首 2int i[100000]; 3int len=0; 4while(ptr != null) 5{ 6 int address = ptr; 7 if(address already in i) 8 { 9 print 链表中存在环; 10 exit(); 11 } 12 i[len] = ptr; 13 ptr = ptr->next; 14} 15print 链表中没有环 16exit();

思路2：如果链表中有环的话，则整个链表呈6、9、或0字形；可以声明两个指向链首的指针，其中一个指针每次移动一个节点，另一个指针每次移动两个节点，如果两个指针指向同一个节点，则表示链表中存在环(类似与小学数学中的追击问题=_=)，否则不存在环。伪代码如下：

1Node * ptr1 = head; 2Node * ptr2 = head; 3if(ptr1 != null) 4 ptr1 = ptr1->next; 5if(ptr1 == ptr2)//考虑链表中只有一个元素，且构成一个环的情况 6{ 7 print 链表中存在环; 8 exit(); 9} 10ptr2 = ptr2->next->next;//或者ptr1->next; 11while(true) 12{ 13 if(ptr1==null || ptr2==null) 14 { 15 print 链表中没有环; 16 break; 17 } 18 if(ptr1==ptr2) 19 { 20 print 链表中存在环; 21 break; 22 } 23 ptr1 = ptr1->next; 24 if(ptr2->next != null) 25 ptr2 = ptr2->next->next; 26} 27exit();