如何找到我不知道大小的循环链表的最后一个节点，并且最后一个节点指向除链表的第一个节点之外的任何其他节点？
Prashant
问问题
6311 次
6 回答
3
根据定义，如果一个节点不指向循环链表的第一个节点，
它就不是最后一个节点。
你能在这里详细说明吗？
于 2009-07-11T20:33:33.053 回答
2
一个奇怪的清单……你为什么需要这样的东西？但不管怎么说...
您可以简单地遍历所有节点，并在下一个节点是您已经访问过的节点时立即停止。当前节点将成为您的答案。
您需要一些方法来跟踪哪些节点已被访问。为每个节点添加一个布尔标志，或者使用某种具有快速插入和查找的集合数据类型（例如散列集）。
于 2009-07-11T20:35:09.617 回答
0
也许将参数添加到列表的节点中，告诉您是否结束？我想，不会有问题的。
否则，您可以记住您已经访问过的节点。当下一个节点已经被访问时，你就在最后。
于 2009-07-11T20:34:22.210 回答
0
Floyd 循环算法不会给出列表的最后一个元素。它只会告诉是否有一个循环。
最后一个的定义是，在从第一个开始的顺序扫描中遍历列表时，它之前的所有元素和最后一个之前都看不到（指针值）。最后一个将是在此顺序扫描中已经看到的第一个元素。
一个简单的解决方案是标记访问过的元素，以便轻松检测到已经看到的元素。该标志可能是侵入性的，即通过更改元素中的位，或者通过使用散列表存储指针值来外部。
由于我们需要能够测试一个元素是否已经被访问过，所以我没有看到其他解决方案。
于 2009-07-14T06:14:26.123 回答
0
我可以详细说明如何使用弗洛伊德算法来解决这个问题，但我不明白一步的解释
- 有 2 个指针遍历链表，指针 1 以每次迭代 1 个节点的速率移动，第二个指针以 2 个节点的速率移动
- 当指针相遇时，我们处于循环中，并且在指针 1 到达循环结束之前有一段距离（我们知道指针 1 尚未到达然后结束，因为如果循环是距离 d 并且指针 2 以两倍的速度移动速度为 1，指针 1 将循环两次，然后指针 1 执行一次）
- 所以因为他们在指针1完全遍历循环之前就已经相遇了，我们知道相遇点是从开始的d个节点和循环内的k个节点（pos = d + k）
- 如果我们将指针 1 设置为位置 0 并再次启动两个点（但以每次迭代 1 个节点的相同速率速率），它们将在循环开始时相遇。
- 因为我们知道循环的开始，所以找到结束是微不足道的
我不完全理解为什么第 4 步是正确的，但我有一个朋友向我解释了解决方案。
于 2011-10-11T13:30:42.193 回答