您当前的位置: 首页 >  数据结构与算法

星拱北辰

暂无认证

  • 0浏览

    0关注

    1205博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

【数据结构与算法】判断单链表是否有环的算法

星拱北辰 发布时间:2020-02-18 22:00:18 ,浏览量:0

带环链表

这里的带环单链表可不是环形单链表,这个环可能是我们不想要的,所以需要检测。 我们就不假设有一个打结状的环了,那样跑到哪里去也不清楚,这里的“带环链表”,环必然是在末端。 这是经典问题,方法众多,但方法效率差别很大,本文试举三例,并对较优算法加以编程实现。

算法一:暴力查重

双指针即可,前一个指针在遍历单链表,后一个指针遍历前指针之前的所有结点是否有与前指针相同的结点。 如果能跑到结尾,自然是无环的,否则就跑下去,总会发现的。 这算法很暴力,不好。

算法二:HashSet查重

不需要双指针,但需要多费一些空间,建一个HashSet,里面装每一个搜索过的结点,搜到的结点如果Set里有,就是说明了有环,否则就把新搜到的结点加入HashSet里面。搜到尽头就是没环。

算法三:双指针

前一个指针一次跳两个结点,后一个结点一次跳一个结点,如果有环,则前后必能相遇。如果前者跑到尽头就说明没环。

算法核心代码(Java语言描述):

private boolean isCircular
关注
打赏
1660750074
查看更多评论
立即登录/注册

微信扫码登录

0.0419s