问题:
如何检查一个单向链表上是否有环?
解答:
1,将所有的遍历过的节点用某个结构存储起来，然后每遍历一个节点，都在这个结构中查找是否遍历过，如果找到有重复，则说明该链表存在循环；如果直到遍历结束，则说明链表不存在循环。
这个结构我们可以使用hash来做，hash中存储的值为节点的内存地址，(java中可以用object.hashcode()做为key放在一个hashtable中. 这样当hashtable中出现重复key的时候说明此链表上有环）这样查找的操作所需时间为O(1)，遍历操作需要O(n)，hash表的存储空间需要额外的O(n)。所以整个算法的时间复杂度为O(n)，空间复杂度为O(n)。
2, 使用反转指针的方法, 每过一个节点就把该节点的指针反向:
bool isLoopbyReverse(Node* head) { Node* cur=head; Node* next=head->next; cur->next=null; while(next!=null) { //如果回到头结点，那么链表有环 if(next==head) { next->next=cur; return ture } //将指针翻转 Node* tmp=cur; cur=next; next=next->next; cur->next=tmp; } //否则的话是没有环的，我们再把链表反转回去 next=cur->next; cur->next=null; while(next!=null) { Node* tmp=cur; cur=next; next=next->next; cur->next=tmp; } return false; }
看上去这是一种奇怪的方法: 当有环的时候反转next指针会最终走到链表头部; 当没有环的时候反转next指针会破坏链表结构(使链表反向), 所以需要最后把链表再反向一次. 这种方法的空间复杂度是O(1), 实事上我们使用了3个额外指针;而时间复杂度是O(n), 我们最多2次遍历整个链表(当链表中没有环的时候).
这个方法的最大缺点是在多线程情况下不安全, 当多个线程都在读这个链表的时候, 检查环的线程会改变链表的状态, 虽然最后我们恢复了链表本身的结构, 但是不能保证其他线程能得到正确的结果.
3, 这是一般面试官所预期的答案: 快指针和慢指针
bool hasLoop(Node* head) { Node* pf=head;//定义快指针，每次移动两个节点 Node* ps=head;//定义慢指针，每次移动一个节点 while(true) { if(pf && pf->next) pf=pf->next->next; else return false; ps=ps->next; //快指针如果和慢指针相遇，则说明有环 if(pf==ps) return true; } }
需要说明的是, 当慢指针(ps)进入环之后, 最多会走n-1步就能和快指针(pf)相遇, 其中n是环的长度. 也就是说快指针在环能不会跳过慢指针, 这个性质可以简单的用归纳法来证明.
(1)当ps在环中位置i, 而pf在环中位置i-1, 则在下一个iteration, ps会和pf在i+1相遇.
(2)当ps在环中位置i, 而pf在环中位置i-2, 则在下一个iteration, ps在i+1, pf在i, 于是在下一个iteration ps和pf会相遇在i+2位置
(3)和上面推理过程类似, 当ps在i, pf在i+1, 则他们会经过n-1个iteration在i+n-1的位置相遇. 于是慢指针的步数不会超过n-1.
确定了一个链表有环，我们如何找到环的开始节点? 如何解开这个环? 这些问题的本质就是如何找到有"回边"的那个节点.
两个指针在环内第一次相遇后，继续在环内移动，当它们再一次相遇时所经过的步数就是这个环的长度，知道了环的长度我们要找到环的开始节点就容易了，我们可以用两个指针，让它们开始时都指向头结点，然后让一个指针向前移动环长的节点，这个时候两个指针同时都以一次移动一个节点的速度向后移动，当它们相遇时，指向的那个节点就是环的开始节点
//计算环的长度 int i=0; do { ps=ps->next; pf=pf->next->next; i++ }while(ps!=pf); //此时i保存的就是环的长度，用两个相距i的指针来找到环的开始节点 ps=head; pf=head; int j; for(j=0;j<i;j++) pf=pf->next; j=0;//将j的值重新赋为0，用j来保存ps，pf相遇时移动的次数 while(ps!=pf) { ps=ps->next; pf=pf->next; j++ } cout<<"环的开始位置是："<<j<<endl; //解开环,此时ps，pf都指向环的开始节点，所以移动其中一个指针到环的末尾 for(j=0; j<=i; j++) { ps = ps->next; } ps->next = NULL;