查找链接列表中是否没有两个指针的循环 [英] find whether a loop in a linked list without two pointers

问题描述

查找链接列表中是否存在循环.你还有其他方法吗 而不是使用快速指针和慢速指针?

find whether there is a loop in a linked list. Do you have other ways instead of using a quick pointer and a slow pointer?

推荐答案

有多种方法可以执行此操作，具体取决于您的情况.

There are a variety of ways you can do this, depending on your situation.

1. 在到达每个节点时将其添加到某种Set中.遍历列表，直到到达末尾或在Set中找到一个节点.

1. Add each node to a Set of some kind when you reach it. Go through the list until you reach the end or find a node already in the Set.

如果节点中有可用空间，则可以将每个节点标记为已访问"，也可以不标记为已访问"，直到找到已标记的节点.

If you have spare space in the nodes, you can mark each node as "visited" or not and walk the list until you find one you've already marked.

当然，这些都有缺点(例如高内存使用)或无法使用的情况，而两指针方法不使用额外的内存，并且几乎可以在任何地方使用.

These, of course, all have downsides (like high memory use) or situations where they're not usable, while the two-pointer method doesn't use extra memory and is applicable pretty much everywhere.

这篇关于查找链接列表中是否没有两个指针的循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！