Given below an example of Singly linked list which contains loop
node_1 --> node_2 --> node_3 --> node_4 --> node_5 --> node_3
i want to detect whether loop exists or not for any given linked list by taking performance factor into consideration .
1
-
possible duplicate of How to determine if a linked list has a cycle using only two memory locationsFlexo - Save the data dump– Flexo - Save the data dump ♦2011-10-07 10:41:54 +00:00Commented Oct 7, 2011 at 10:41
Add a comment
|
2 Answers
Initialize a hash. Iterate over the list. For each node, if it's already in the hash, return LOOP. Otherwise, add it to the hash. When end of list is reached, return NO_LOOP.
Note: you don't have to put the entire node in the hash. An identifier is enough, or anything else that identifies the node uniquely.
answered Oct 7, 2011 at 10:42
Eran Zimmerman Gonen
4,5171 gold badge22 silver badges32 bronze badges
4 Comments
Flexo - Save the data dump
I think that's less efficient than Floyd's cycle finding algorithm since it's O(n) storage
Eran Zimmerman Gonen
It uses more memory, but its actual running time should be shorter (even though they're both O(n)).
Flexo - Save the data dump
I guess it depends how big the subset that forms the loop is, if it exists. I suspect it's one of those things that in the real world you'd pick one for certain sized lists and another for the others after measuring actual implementations.
kedar kamthe
@EranZimmerman: This will use more memory if list size is more than 10000 (suppose).storing data to other data structure should be avoided and we should avoid modification of data in Node too.
function boolean hasLoop(Node startNode){
Node slowNode = Node fastNode = startNode;
while(true){
if(slowNode)
return false;
else if(((slowNode==fastNode)&&fastNode!=startNode)||fastNode->next==slowNode)
return true;
else{
slowNode=slowNode->next;
fastNode=fastNode->next->next;
}
}
}