关于 “怎样才能检测到链表中存在循环” （某人说微软面试题目）

pcl2004_27

面试题目是否要表达的是这个意思： 有一个单链表可能包含有循环，可能没有循环，怎么样设计一个算法判断它是否有循环。


设两个指针，一个步长为1，一个步长为2，在单链表中向后移动，如果链表中有循环，则两个指针肯定会相遇
理由：假设3个元素的链表中第2个元素的后面是第1个元素。设置两个指针p1和p2，p1指向第1个元素，p2指向第3个元素，看看它们是否相等。如果相等就属于上述这种特殊情况。如果不等，把p1向后移一个元素，p2向后移两个元素。检查两个指针的值，如果相等，说明链表中存在循环。如果不相等，继续按照前述方法进行。如果出现某个指针是NULL的情况，说明链表中不存在循环。如果链表中存在循环，用这种方法肯定能够检测出来，因为在单链表的环中其中一个指针肯定能够追上另一个（两个指针具有相同的值）。


if (head==NULL) return true;

p=head; q=head->next;
while (q!=nil && q->next!=nil && p!=q){
    p=p->next;
    q=q->next->next;
}

if (p==q) return false;
else return true;

于淼

首先不得不说：老朴强啊！！！！！！！！！！
我当时咋就没想到这个方法呢？

另外回答nishuangxi 和JaneGu 的话，如果链表中的循环节点是3000指向1000，你怎么确定P1在哪里？
不然老朴应该不会用这么复杂的指针

JaneGu

原帖由 nishuangxi 于 2006-11-7 21:13 发表
P1完全可以不移动，只是移动P2，P2＝P2－>next，知道p1＝p2停止也可以吧。

我同意！P2＝P1或P2＝NULL就停止，P2＝P1为存在循环，P2＝NULL为不存在循环。


如果这个单链表存在n个元素，（n>=1）P2在P1之前一步，则需n-1次P2可追上P1（如果存在循环的话）。 P1不移动的话也一样需n-1次。

nishuangxi

P1完全可以不移动，只是移动P2，P2＝P2－>next，知道p1＝p2停止也可以吧。

zhou840401

说得有理,由于p1向后移1个元素,p2向后移2个元素,每次移动之后,p2就比p1相差远1个元素,到了最后,如果链表是循环的话,到了最后p2肯定能够从后面追上p1

wssgily

思路真是好啊!