c - 单次遍历中链接列表的中点？

Question

我试图找到循环开始的单链接列表的点。我想到的是用 2 个指针 *慢，*快，一个以两倍于另一个的速度移动。如果列表有一个循环，那么在某个时候

    5-6-7-8
    |     |
1-2-3-4-7-7

慢=快

是否有另一种优雅的解决方案，以便列表只遍历一次？

Answer 1

您使用两个walker 的想法，其中一个的速度是另一个的两倍会起作用，但是这提出的更基本的问题是您是否选择了合适的数据结构？您应该问自己是否真的需要找到中点，如果需要，还有哪些其他结构可能更适合在 O(1)（恒定）时间内实现这一目标？数组肯定会为集合的中点提供更好的性能，但其他操作速度较慢。在不了解其余上下文的情况下，我无法提出任何其他建议，但我建议您查看您的要求。

Answer 2

我假设这个单链表以 NULL 结尾。在这种情况下，慢指针和快指针都会起作用。因为快指针的速度是慢指针的两倍，所以如果快指针到达列表末尾，慢指针应该在它的中间。

Answer 3

我假设这是某种面试问题。

如果您的列表有一个循环，那么要在一次遍历中完成，您需要在快速步行者通过列表时将节点标记为已访问。当 fast walker 遇到 NULL 或已经访问过的节点时，迭代可以结束，而你的 slow walker 处于中点。

有很多方法可以将节点标记为已访问，但可以使用外部地图或集合。如果您直接在节点本身中标记节点，则需要再次遍历以清理标记。

编辑：所以这不是关于找到中点，而是关于循环检测而不重新访问已经访问过的节点。标记也适用于此。只需遍历列表并标记节点。如果你命中 NULL，则没有循环。如果你点击一个访问过的节点，就会出现一个循环。如果标记还包括一个计数器，您甚至可以知道循环从哪里开始。