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

Question

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

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

慢=快

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

Answer 1

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