如何找到一个大小未知的循环链表的最后一个节点，且最后一个节点指向除了链表的第一个节点以外的任何其他节点？
寻找一个大小未知、且尾节点指向链表中除第一个节点之外任何其他节点的循环链表的最后一个节点
4
- Prashant
1
3如果一个节点指向另一个节点而不是第一个节点，那么它怎么成为最后一个节点呢？ - nik
6个回答
3
根据定义，如果一个节点不指向循环链表的第一个节点，它就不是最后一个节点。
你能在这里详细说明一下吗？
- nik
6
1我认为这是因为我们称其为“循环”，不是吗？ - Jonathan
5他的意思很清楚：一个链表，其中“最后一个节点”指向列表中的某个非第一个节点，使其成为Q形状。不知道为什么或如何获得这样的列表。 - Sean
你可以形成“Q”和椒盐脆饼。循环列表直到到达头部才结束。如果在没有到达头部的情况下结束列表，则该列表不再是循环的。 - nik
在这种情况下，为了得到一个恰当的答案，最好获得列表的清晰描述。 - nik
实际上，除非你有一个节点可以指向多个后继节点的列表，否则你无法拥有一个椒盐脆饼形状的列表。无论如何，虽然它不是严格意义上的循环，但如果你有一个明确定义的头部，那么你明确定义的结尾就是从头部开始遍历列表时到达的最后一个新节点。我认为称呼一个Q形状的列表为“循环”，然后通过说它有一个尾巴或者OP中的措辞来限定它是有效的。我同意更多的细节会更好，但我也感觉这是一个作业或面试题。 - Sean
一个循环链表不一定要将最后一个节点连接到第一个节点。最后一个节点可以指向列表中的任何节点，包括它自己以及头部。 - Oleksiy
2
一个奇怪的列表...为什么需要这样的东西？但是不管怎样...
你可以简单地遍历所有节点，当下一个节点是你已经访问过的节点时停止。当前节点就是你的答案。
你需要一些方法来跟踪哪些节点已经被访问。向每个节点添加一个布尔标记，或使用某种具有快速插入和查找功能的集合数据类型（例如哈希集）。
- Thomas
0
也许可以在列表的节点中添加一个参数，告诉你是否到达了末尾？我认为这不会成为问题。
否则，你可以记住已经访问过的节点。当下一个节点已经被访问过时，你就到达了末尾。
否则，你可以记住已经访问过的节点。当下一个节点已经被访问过时，你就到达了末尾。
- izidor
0
Floyd循环算法无法返回列表的最后一个元素，它只能告诉我们是否存在循环。
最后一个元素的定义是，在从第一个元素开始顺序扫描列表时，它之前和最后一个元素之前的所有元素都没有被看到过（指针值）。在最后一个元素之后的第一个元素将是在此顺序扫描中已经被看到的第一个元素。
一种简单的解决方案是标记已访问的元素，这样就可以轻松检测到已经看到的元素。标记可以是侵入式的，即通过更改元素中的位，也可以是外部的，通过使用哈希表来存储指针值。
由于我们需要能够测试元素是否已经被访问过，我认为没有其他解决方案。
- chmike
0
我可以详细讲解如何使用 Floyd 算法来解决这个问题，但我不理解其中一个步骤的解释。
- 有两个指针遍历链表，第 1 个指针每次迭代移动 1 个节点，第二个指针每次迭代移动 2 个节点
- 当指针相遇时，我们在循环中，并且我们离指针 1 到达循环结尾的距离还有一段距离（因为如果循环的距离为 d，指针 2 的速度是指针 1 的两倍，那么指针 1 在指针 2 回到相遇点之前会绕着循环走两圈，而指针 2 只绕一圈）
- 因此，因为它们在指针 1 完全遍历循环之前相遇，所以我们知道相遇点距离起点 d 个节点，在循环内部 k 个节点（pos = d + k）
- 如果我们将指针 1 设置为位置 0 并重新开始两个指针（但速度相同，每次迭代移动 1 个节点），它们将在循环开头相遇。
- 由于我们知道循环的起始点，所以找到结束点很容易
我不完全理解为什么步骤 4 是正确的，但我有一个朋友向我解释了这个解决方案。
- i8abug
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接