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 .

possible duplicate of [How to determine if a linked list has a cycle using only two memory locations](http://stackoverflow.com/questions/494830/how-to-determine-if-a-linked-list-has-a-cycle-using-only-two-memory-locations) — Flexo, Oct 07 '11 at 10:41

score 1 · Answer 1 · answered Oct 07 '11 at 10:42

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.

answered Oct 07 '11 at 10:42

Eran Zimmerman Gonen

4,375
1
19
31

I think that's less efficient than Floyd's cycle finding algorithm since it's O(n) storage – Flexo Oct 07 '11 at 10:44
It uses more memory, but its actual running time should be shorter (even though they're both O(n)). – Eran Zimmerman Gonen Oct 07 '11 at 10:49
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. – Flexo Oct 07 '11 at 10:58
@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. – kedar kamthe Oct 10 '11 at 09:43

score 0 · Accepted Answer · answered Oct 13 '11 at 12:41

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

Pseudo logic to Detect loop in Singly linked list

2 Answers2