Jav*_*per 2 java algorithm linked-list data-structures singly-linked-list
这个问题与找到2个链表的交集有点不同.
考虑一个带循环的链表:A - B - C - D - E - F - C.
如果node A是函数的输入,那么它应该返回C.
由于我不知道该怎么称呼C,我使用了一个术语循环节点,C如问题中所示.虽然O(n 2)项似乎很明显,但是有没有办法找到复杂度较低的循环节点？
不允许使用O(n)的哈希表/额外空间.
有一个使用两个指针的简单方法.第一个指针以慢速指针的速度增加一秒和二.
所以在你的情况下链表实际上是A-> B-> C-> D-> E-> F-> C意味着F再次指向C.So方法如下
1.保持增加两个指针直到它们匹配.所以在上面的例子中我们将有这些步骤
慢指针:ABCDE
快速指针:ACECE
所以我们停在E处,这表明有一个循环.现在我们需要找到循环节点.
现在从E移动指向链表开始的慢指针并创建一个指向E的新指针,并且还增加1.这两个指针相遇的点实际上是循环节点.所以在我们的例子中
指针从一开始:ABC新指针:EFC
所以当你看到他们在C会面时我们已经完成了在链表中找到循环节点.
更新: 对于这种方法的数学证明,请参考这个精彩的问题,并看看@Jim Lewis回答了答案下面的所有评论.解释循环链表中查找循环开始节点的工作原理？