标题:检测链表是否为循环链表


问题:如何判断一个单向链表是否存在循环?

这个问题反复出现在历次名企求职笔试和面试中。本人就在不同时间参加某TOP2 IT公司的笔试和面试的时候都遇到了这个问题。足见这个问题是多么的经典。

2个方法来判断一个单向链表中是否存在循环:

算法1:该算法为步长法判断链表是否存在循环,即设两个遍历,第一个遍历步长是第二个遍历的步长的两倍,如果这两个遍历相遇(遍历到同一个节点),则单链表有环路。

 

int FindLoop(node *head)

{


}

算法1能够判断链表中是否含有循环,但是它不能准确的判断循环出现的位置。于是便有了新的算法2。在算法2中不但能够判断链表中是否含有循环,还能找出循环出现的具体位置。

算法2:当链表里当前的node的下一个node不是前面的任何一个node(包括自己),那么这个链表就不是循环链表,反之则包含了循环。

 

node *FindLoop(node *head)

{


}

注意:算法部分是麦洛科菲基础部分重点培训的内容,每一个点都可能成为麦洛科菲考试,作业的组成部分。所以,我们不提供具体的解法。如果您对某个点有疑问,请随时联系我们。


看文字不过瘾?点击我,进入腾讯课堂视频教学
麦洛科菲长期致力于IT安全技术的推广与普及,我们更专业!我们的学员已经广泛就职于BAT360等各大IT互联网公司。详情请参考我们的 业界反馈 《周哥教IT.C语言深学活用》视频

我们的微信公众号,敬请关注