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 to search but couldn't find a satisfactory solution. If possible, can you provide a pseudo-code or Java-implementation?

For instance:
1 → 3 → 5 → 71 → 45 → 7 → 5, where the second 5 is actually the third element of the list.

Answer 1

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 -- off 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 2

A simple algorithm called Floyd's algorithm is to have two pointers, a and b, which both start at the first element in the linked list. Then at each step you increment a once and b twice. Repeat until you either reach the end of the list (no loop), or a == b (the linked list contains a loop).

Another algorithm is Brent's algorithm.

Answer 3

Three main strategies that I know of:

1. Starting traversing the list and keep track of all the nodes you've visited (store their addresses in a map for instance). Each new node you visit, check if you've already visited it. If you've already visited the node, then there's obviously a loop. If there's not a loop, you'll reach the end eventually. This isn't great because it's O(N) space complexity for storing the extra information.

2. The Tortoise/Hare solution. Start two pointers at the front of the list. The first pointer, the "Tortoise" moves forward one node each iteration. The other pointer, the "Hare" moves forward two nodes each iteration. If there's no loop, the hare and tortoise will both reach the end of the list. If there is a loop, the Hare will pass the Tortoise at some point and when that happens, you know there's a loop. This is O(1) space complexity and a pretty simple algorithm.

3. Use the algorithm to reverse a linked list. If the list has a loop, you'll end up back at the beginning of the list while trying to reverse it. If it doesn't have a loop, you'll finish reversing it and hit the end. This is O(1) space complexity, but a slightly uglier algorithm.

Answer 4

I you count your Nodes and get to the *head again.

Answer 5

Use the Tortoise-Hare algorithm.

Answer 6

How about following approach:

Sort the link list in ascending order by following any standard algorithms. Before sort: 4-2-6-1-5 After Sort: 1-2-4-5-6

Once sorted, check for each node data and compare with link node's data, something like this:

if(currentcode->data > currentnode->link->data) i.e. circular = true;

At any comparison, if any of "currentnode->data" is greater than "currentcode->link->data" for a sorted link list, it means current node is pointed to some previous node(i.e circular);

Guys, i dont have setup to test the code.Let me now if this concept works.

Answer 7

A algorithm is:

1. Store the pointer to the first node
2. Traverse through the list comparing each node pointer to this pointer
3. If you encounter a NULL pointer, then its not circularly linked list
4. If you encounter the first node while traversing then its a circularly linked list

Answer 8

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 9

@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 10

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 11

It will never terminate from the loop, it can 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;
    }
}

Answer 12

Try this

/* Link list Node */

struct Node { int data; struct Node* next; };

/* This function returns true if given linked list is circular, else false. */ bool isCircular(struct Node *head) { // An empty linked list is circular if (head == NULL) return true;

// Next of head
struct Node *node = head->next;

// This loop would stope in both cases (1) If
// Circular (2) Not circular
while (node != NULL && node != head)
   node = node->next;

// If loop stopped because of circular
// condition
return (node == head);

}