带环单链表的故事
@不了解前尘往事的Reader,烦请阅读——《判断单链表是否有环的算法》
如何找带环单链表的环的入口这里只说比较可行的算法吧。
思路一:HashSet第一个重复元素就是环的入口按照查找单链表带环的思路二,我们用一个HashSet维护已经跑过的元素,当重复的时候,那个结点就是环的入口。这法子还算好使,不过还是老问题——空间复杂度大。
思路二:再开一个指针与当前指针相会我们当前双指针停在交汇处,这里有一个位置。
思来想去我还是给大家画个图吧:
有两个画错的地方:就是其实l1应该由node4画到node7,再就是node6上的线应该把焦点改到node7。
大家也读过上面的文章应该也知道我的测试数据是: node1 → node2 → node3 → node4 → node5 → node6 → node7 → node8 → node9 → node4
。