求一个验证单向链表是否出现循环错误的最优算法

yf_boy

题目:有一个很长的单向链表a-->;b-->;c-->;........-->;d.........-->;e，由于某些错误导致e节点链接到中间一个节点如d,现在验证这个单向是否出现循环，请问有什么比较好的算法.

小弟比较愚昧,只有想出来最笨的办法,就是遍历链表,把新的节点和前面的节点相比较看是否有相同的,一直遍历到尾节点,如果有相同的说明链表循环了,如果有尾节点说明链表是正确的.

flw

搜索老帖，tooooooooooold！

lingboj

大家一起交流一下。
单链表，我不知道。
双链表，没有问题。
p=header;
while(p->;next->;pre==p && p->;next!=NULL)
      P=P->;next;
if(p->;next!=NULL)
      printf("error:find dead loop\n";

faint_u

多经典的面试题阿，两个指针，一个两步走，一个一步走，如果相遇说明有环，否则没有

redwin

一个快指针,一个慢指针,就是一个走两步,一个走一步,看看能否相等.

lingboj

Why I couldn't think ?

faint_u

说实话这个题目确实很难，不过大部分人都听说过

bleem1998

专家编程里的那个？

yf_boy

555555,我没听过,平时看书还不够啊.结果面面的时候就出糗了....