What is an efficient algorithm to find whether a singly linked list is circular/cyclic or not?

Question

How can i find whether a singly linked list is circular/cyclic or not? I Tried searching but couldn't find a satisfactory solution. If possible, can you provide pseudocode or Java?

For Example 1 3 5 71 45 7 5 -stop , its a circular linked list

Answer 1

Start at one node and record it, then iterate through the entire list until you reach a null pointer or the node you started with.

Something like:

Node start = list->head;
Node temp = start->next;
bool circular = false;
while(temp != null && temp != start)
{
   if(temp == start)
   {
     circular = true;
     break;
   }
   temp = temp->next;
}
return circular

This is O(n), which is pretty much the best that you will able to get with a singly linked list (correct me if I'm wrong).

Or to find any cycles in the list (such as the middle), you could do:

Node[] array; // Use a vector or ArrayList to support dynamic insertions
Node temp = list->head;
bool circular = false;
while(temp != null)
{
   if(array.contains(temp) == true)
   {
     circular = true;
     break;
   }
   array.insert(temp);
   temp = temp->next;
}
return circular

This will be a little bit slower due to the insertion times of dynamic arrays.

Answer 2

The standard answer is to take two iterators at the beginning, increment the first one once, and the second one twice. Check to see if they point to the same object. Then repeat until the one that is incrementing twice either hits the first one or reaches the end.

This algorithm finds any circular link in the list, not just that it's a complete circle.

Pseudo-code (not Java, untested -- of the top of my head)

bool hasCircle(List l)
{
   Iterator i = l.begin(), j = l.begin();
   while (true) {
      // increment the iterators, if either is at the end, you're done, no circle
      if (i.hasNext())  i = i.next(); else return false;

      // second iterator is travelling twice as fast as first
      if (j.hasNext())  j = j.next(); else return false;
      if (j.hasNext())  j = j.next(); else return false;

      // this should be whatever test shows that the two
      // iterators are pointing at the same place
      if (i.getObject() == j.getObject()) { 
          return true;
      } 
   }
}

Answer 3

How hard have you searched? This is in C++, but it will be trivial to convert in Java.

Answer 4

@samoz has in my point of view the answer! Pseudo code missing. Would be something like

yourlist is your linked list

allnodes = hashmap
while yourlist.hasNext()
   node = yourlist.next()
   if(allnodes.contains(node))
      syso "loop found"
      break;
   hashmap.add(node)

sorry, code is very pseudo (do more scripting then java lately)

Answer 5

Search for the Tortoise-Hare algorithm/description.

Answer 6

Here is a nice site on which the different solutions can copied.

find loop singly linked list

This is the winner on that site

// Best solution
function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

This solution is "Floyd's Cycle-Finding Algorithm" as published in "Non-deterministic Algorithms" by Robert W. Floyd in 1967. It is also called "The Tortoise and the Hare Algorithm".

Answer 7

hey it will never terminate from the loop,

it con also be done in following solution

bool hasCircle(List l) { Iterator i = l.begin(), j = l.begin(); while (true) { // increment the iterators, if either is at the end, you're done, no circle if (i.hasNext()) i = i.next(); else return false;

  // second iterator is travelling twice as fast as first
  if (j.hasNext())  j = j.next(); else return false;
  if (j.hasNext())  j = j.next(); else return false;

  // this should be whatever test shows that the two
  // iterators are pointing at the same place
  if (i.getObject() == j.getObject()) { 
      return true;
  } 

if(i.next()==j) break; } }