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

星拱北辰

暂无认证

  • 0浏览

    0关注

    1205博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

【数据结构与算法】带环单链表查找环的入口算法

星拱北辰 发布时间:2020-02-19 00:04:25 ,浏览量:0

带环单链表的故事

@不了解前尘往事的Reader,烦请阅读——《判断单链表是否有环的算法》

如何找带环单链表的环的入口

这里只说比较可行的算法吧。

思路一:HashSet第一个重复元素就是环的入口

按照查找单链表带环的思路二,我们用一个HashSet维护已经跑过的元素,当重复的时候,那个结点就是环的入口。这法子还算好使,不过还是老问题——空间复杂度大。

思路二:再开一个指针与当前指针相会

我们当前双指针停在交汇处,这里有一个位置。

思来想去我还是给大家画个图吧: 在这里插入图片描述

有两个画错的地方:就是其实l1应该由node4画到node7,再就是node6上的线应该把焦点改到node7。

大家也读过上面的文章应该也知道我的测试数据是: node1 → node2 → node3 → node4 → node5 → node6 → node7 → node8 → node9 → node4

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

微信扫码登录

0.0455s