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

Question

我试图找到循环开始的单链接列表的要点.我想到的是2个指针*慢,*快速移动速度是其他速度的两倍.如果列表在某个时刻有循环

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

慢=快

可以有另一个优雅的解决方案,以便列表只遍历一次？

Answer 1

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

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

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

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