© 1999-2048 dssz.net 粤ICP备11031372号
[其它] 带环单链表查找环的入口算法(Java语言描述)
说明:带环单链表的故事 不了解前尘往事的Reader,烦请阅读——《判断单链表是否有环的算法》 如何找带环单链表的环的入口 这里只说比较可行的算法吧。 思路一:HashSet第一个重复元素就是环的入口 按照查找单链表带环的思路二,我们用一个HashSet维护已经跑过的元素,当重复的时候,那个结点就是环的入口。这法子还算好使,不过还是老问题——空间复杂度大。 思路二:再开一个指针与当前指针相会 我们当前双指针停在交汇处,这里有一个位置。 思来想去我还是给大家画个图吧: 有两个画错的地方:就是其实l1应<weixin_38734361> 上传 | 大小:99kb