Pseudo logic to Detect loop in Singly linked list

Question

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 .

• Flexo - Save the data dump: possible duplicate of How to determine if a linked list has a cycle using only two memory locations

Answer 1

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.

• 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.

Answer 2

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;
 }
 }
 }