链表...... [英] linked list...
问题描述
如何在单个链表中找到循环？
我想过多次保留一个标记或遍历列表...但是
它将需要另一种存储所有这些东西的数据结构......
如果列表中有很多节点，那么这就不会有问题。
那么有完整的证据吗解决方案？
How can I find a loop in a single linked list?
I thought about keeping a flag or traversing list more than once...but
it will require another data structure to store all these things...
Also if the list is having many nodes then this won''t ork..
So is there a full proof solution?
推荐答案
6月20日晚上10点11分，Shraddha< shraddhajosh ... @ gmail.comwrote：
On Jun 20, 10:11 pm, Shraddha <shraddhajosh...@gmail.comwrote:
如何在单个链表中找到一个循环？
我想过多次保留一个标志或遍历列表......但是
它将需要另一个数据结构来存储所有这些东西...
如果列表中有很多节点，那么这就不会是ork ..
那么有完整的证明解决方案吗？
How can I find a loop in a single linked list?
I thought about keeping a flag or traversing list more than once...but
it will require another data structure to store all these things...
Also if the list is having many nodes then this won''t ork..
So is there a full proof solution?
尝试野兔和乌龟的方法。基本上有2个ptrs
指向列表的开头。将一个指针递增1并将另一个指针递增2.另一个递增comapre如果它们相等。如果
指针会有一个循环。
Try the Hare and Tortoise approach. Basically have 2 ptrs both
pointing to the start of the list. Increment one pointer by 1 and
another by 2. After each increment comapre if they are equal. If
there is a loop the pointers would meet.
6月21日上午7:11，Shraddha< shraddhajosh ... @ gmail.comwrote：
On Jun 21, 7:11 am, Shraddha <shraddhajosh...@gmail.comwrote:
如何在单个链表中找到循环？
我想保留一面旗帜或者多次遍历列表...但是
它将需要另一个数据结构来存储所有这些东西......
如果列表中有很多节点那么这个不会ork ..
How can I find a loop in a single linked list?
I thought about keeping a flag or traversing list more than once...but
it will require another data structure to store all these things...
Also if the list is having many nodes then this won''t ork..
如果你可以修改列表中的节点，你可以添加一个标志，
visit，初始化为false。循环，设置标志
true，直到找到列表的结尾，或者
标志为true的节点。如果你遇到了列表的末尾，那就没有
循环，循环再次将标志重置为false（下次）。
如果遇到节点标志为true，有一个循环。
重置标志，从头开始循环，直到你遇到
a节点并重置标志。
如果你不能修改列表中的节点，你需要一些
的后备缓存，节点的地址已经
内存。
-
James Kanze（GABI软件） ，来自CAI）电子邮件：ja ********* @ gmail.com
Conseils eninformatiqueorientéeobjet/
Beratung in objektorientierter Datenverarbeitung
9个地方Sémard，78210 St.-Cyr-l''coco，法国，+ 33（0）1 30 23 00 34
If you can modify the nodes in the list, you can add a flag,
visited, which is initialized false. Loop, setting the flag
true, until you find the end of the list, or a node with the
flag true. If you encountered the end of the list, there''s no
cycle, loop again resetting the flag false (for the next time).
If you encountered a node with the flag true, there''s a cycle.
To reset the flags, loop from the beginning, until you encounter
a node with the flag reset.
If you can''t modify the nodes in the list, you''ll need some sort
of look-aside cache with the addresses of the nodes already
visited; if the list is long, this could require a lot of extra
memory.
--
James Kanze (GABI Software, from CAI) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l''école, France, +33 (0)1 30 23 00 34
James Kanze写道：
James Kanze wrote:
>
如果你可以修改列表中的节点，你可以添加一个标志，
访问
，初始化为false。循环，设置标志
true，直到找到列表的结尾，或者
标志为true的节点。如果你遇到了列表的末尾，那就没有
循环，循环再次将标志重置为false（下次）。
如果遇到节点标志为true，有一个循环。
重置标志，从头开始循环，直到你遇到
a节点并重置标志。
>
If you can modify the nodes in the list, you can add a flag,
visited, which is initialized false. Loop, setting the flag
true, until you find the end of the list, or a node with the
flag true. If you encountered the end of the list, there''s no
cycle, loop again resetting the flag false (for the next time).
If you encountered a node with the flag true, there''s a cycle.
To reset the flags, loop from the beginning, until you encounter
a node with the flag reset.
如果你还保留一个
标志告诉你离开访问过的节点的状态，你不需要第二次循环。最后一次。
在开始主循环之前，你切换那个标志的值，然后通过节点检查节点的标志是否等于该值来获得
外部
标志;如果是这样，你就有了一个循环;如果没有，将节点的标志设置为等于
外部标志。
-
- Pete
Roundhouse Consulting，Ltd。（ www.versatilecoding.com ）
标准C ++库扩展：教程和
参考的作者。 （ www.petebecker.com/tr1book ）
这篇关于链表......的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
