如何找到其中有环的链表的长度？
这是面试时提出的问题之一。如何找到其中有循环的链表的长度。我知道如何使用兔子和乌龟技术来计算链表是否有循环。我什至知道如何通过将地址存储在哈希集中来计算长度。算法的运行时间应该是 O(n)。
但我无法告诉的是如何在不使用 O(n) 外部空间的情况下计算链表的长度。请帮我。谢谢。
This was one of the interview questions asked. How to find the length of a linked list that is having cycle in it. I know how to calculate whether a linked list has a cycle or not using Hare and Tortoise technique. I even know how to calculate the length by storing the addresses in a hashset. The running time of the Algorithm should be O(n).
But what I was not able to tell is how to calculate the length of the linked list without using a external space of O(n). Please help me. Thank you.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
我认为如果你知道循环的起始节点，你就可以知道循环的长度，从而知道链表中的节点总数。
为了获得起点，您只需要 O(1) 空间。
假设你的两个指针，快指针和慢指针在“节点 t”处相遇。
增加一个指针以指向下一个节点。
另一个指针指向链表的开头。
现在增加两个指针直到它们相遇。
交汇点是循环的起始节点。
由此，您可以通过再次遍历来获取循环长度，因为您知道循环的起点。
I think If some how you know the starting node of cycle , you can know the length of cycle and hence the total number of nodes in linked list.
For getting starting point you need only O(1) space.
Suppose your two pointers,fast and slow met at 'node t'.
increment one pointer to point to next node.
and the other pointer to start of linked list.
Now increment both the pointers until they meet.
The meeting point is starting node of cycle.
From this you can get the Length of cycle by traversing again since you know the starting point of cycle.
检测到循环后，您需要计算循环的长度及其开始的位置。这些的总和就是列表中不同节点的总数。详细信息例如：http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare
Once you've detected the cycle, you need to calculate the length of the cycle, and the position at which it starts. The sum of these is the total number of distinct nodes in the list. Details for example here: http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare
反向链接的数量就是循环的长度
The number of reversed links is the length of the cycle
检测循环点
通过（慢指针和快指针的方法），找到环路检测节点
现在取指针P1和P2，P1在环路检测节点，P2从链表头开始
一次遍历两个指针
两个指针在链表中出现循环的节点处相遇
使用标准的快慢指针算法找到循环检测点
在循环检测点取两个指针 P1 和 P2。将指针 P1 放在同一位置，然后将 P2 向前移动一步。重复直到两个指针相遇。为每次迭代保留一个递增的计数变量，该变量给出了循环的长度。假设长度为 L1
再次取两个指针 P1 和 P2。 P1位于链表头部，P2位于环路检测点。将两个指针一次向前推进一步。重复直到两个指针相遇。这个过程相当于我们用来计算链表中导致循环的节点的过程。为每次迭代保留一个递增的计数变量，该变量给出了直到合并点的列表长度。假设长度为 L2
现在包含循环的列表的长度是L1+L2
Detect loop point
By (Slow pointer and fast pointer approach), find the loop detection node
Now take pointers P1 and P2, P1 at the loop detection node and P2 starting from head of the linked list
Traverse both the pointers one at a time
Both the pointers meet at the node because of which there is a loop in the linked list
Use the standard fast and slow pointer algorithm find the loop detection point
Take two pointers P1 and P2 at loop detection point. Place pointer P1 at the same place and move P2 forward one step at a time. Repeat until both the pointers meet together. Keep a count variable incremented for every iteration which gives length of the loop. Let say the length is L1
Again take two pointers P1 and P2. P1 at the head of the linked list and P2 at the loop detection point. Forward both the pointers one step at a time. Repeat until both the pointers meet together. This procedure is equivalent to the one we use to calculate node that causes loop in a linked list. Keep a count variable incremented for every iteration which gives the length of the list until the merging point. Let say the length is L2
Now the length of the list that contains loop is L1+ L2
以下是流行的兔子和乌龟算法用于查找链表长度的正确性的数学证明。
Here's the mathematical justification of the correctness of the popular hare and tortoise algorithm for finding the length of the linked list.
不会陷入无限循环吗？如果 1 2 3 ... 9 10 形成一个循环，从 1 开始。假设当起始节点的指针到达 1 时，另一个指针在节点 8 处。那么它们的移动如下
指针1：- 1 2 3 4 5 ..
指针2：- 8 9 10 1 2..
显然他们永远不会平等。
wont it go in infinite loop? if 1 2 3 ... 9 10 form a loop ,which starts at 1.Suppose when pointer from start node reaches 1 ,other pointer is at node 8. then they move as
pointer1:- 1 2 3 4 5 ..
pointer2:- 8 9 10 1 2..
clearly they wont ever be equal.