首页 > 试题广场 >

判断一个链表是否存在回路?

[问答题]
判断一个链表是否存在回路?
添加回答
elonqiao头像 elonqiao
这是一个经典面试题，判断一个链表是否有回路？
首先，设置两个指针，从头指针开始走，一个走一步（一个节点），另一个走三步
接着，判断两个指针指向是否相同，如果相同，即存在回路；否则，没有回路。
这个题的升级版是，判断相遇节点在哪？希望能帮到你。。。
发表于 2016-06-21 14:46:08 回复(0)
掉下个小石头头像 掉下个小石头
数学问题，设置一个一次走两步的快指针和一个一次走一步的慢指针。两个指针同时从头结点开始走，如果快指针访问到链表尾节点则不存在环，如果快指针慢指针相遇则存在环。更多相关问题，以及数学解释可以参考这篇博客。
http://blog.csdn.net/zhangzhengyi03539/article/details/50776583
编辑于 2016-06-21 19:12:29 回复(0)
selfim头像 selfim
两个指针，第一个指针每次走一步，第二个指针每次走两步，，当两个指针相遇的时候，表明有回路；
发表于 2016-06-21 10:41:47 回复(0)
卡卡殿下头像 卡卡殿下
设置两个指针pa和pb，从p0节点出发朝同一方向遍历，pa每次往后走一个节点pa=pa->next, pb每次往后走两个节点 pb = pb ->next->next，如果某一时刻 pa == pb则表示有回路，如果pb已经走到链表的末端即pb=null则表示没回路
编辑于 2015-08-11 14:15:22 回复(0)
xxj头像 xxj
追击问题：如链表S,申请两个链表指针p1，p2，初始值都指向S的头部head，循环，p1每次加1，p2每次加2，判断结果，p2指向了空指针：没有回路，p2==p1有回路。
//一下为伪代码：
assert(s != null);
const Node * p1 = S->head,*p2 = S->head;
while(p2)
{
    p2 = p2->next;
    if(p2 == null)
        return false;//没有回路
    p2 = p2->next;
    //此处可以跳出循环，返回有回路，故不需要判断
    //if(p2 == null)
    //    return false;//没有回路
    p1 = p1->next;
    if(p1 == p2)
        return true;//有回路
}

return false;
发表于 2015-03-09 12:09:33 回复(0)
神经咩头像 神经咩
给指针加一个标志域，如访问过则置1.当遍历到标志为1的项说明有了回路。
发表于 2014-10-25 00:26:05 回复(0)
提交观点

问题信息

链表 百度
上传者：霰雪繁天
难度：
6条回答 7147浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号