CODEWITHSUNDEEP
data-structures
kedar kamthe
kedar kamthe

Reputation: 8178

Pseudo logic to Detect loop in Singly linked list

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 .

Upvotes: 1

Views: 415

Answers (2)

kedar kamthe
kedar kamthe

Reputation: 8178

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

Upvotes: 0

Eran Zimmerman Gonen
Eran Zimmerman Gonen

Reputation: 4507

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.

Upvotes: 1

Related Questions