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

Question

This question already has answers here:

How to detect a loop in a linked list? (29 answers)

Closed 8 years ago.

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.

• kgiannakakis: How hard have you searched? This is in C++, but it will be trivial to convert in Java.
• Steve Jessop: @kd304: no, in most implementations the list isn't circular. It has a first and last element, and it's not valid for clients to walk off the ends. The data structure used internally to implement the list may be a circular list (with a way of recognising the head when you get back to it). Important distinction between two different levels of abstraction.
• aberrant80: I don't understand the example... what's circular about it?
• Mark Byers: What do you mean by circular? Do you mean that it contains a loop, or that it is a loop?
• Vlad H: There should be more details. Do you have control over elements structure (ie. can you add a new field)? Do you need to check only for purely circular (ie. the last element points back to head) or also circular sublists?

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

• Jon Skeet: The good thing about this is it spots cycles which aren't necessarily at the start, whereas the "check until you reach head again" only spots a fully circular list.
• Vilx-: Nice, hadn't thought of this before! :)
• Bill the Lizard: @teabot: It's called Floyd's Cycle-Finding Algorithm, but it's sometimes referred to as "The Tortoise and the Hare Algorithm".
• starblue: In math this algorithm is sometimes used for loop finding, for example in factoring large numbers. There it is called after the greek letter rho, for the similarity to the shape of the search space with an initial part and loop at the end (i.e. Pollard's rho algorithm).
• RichardOD: Here's the wikipedia page for it- en.wikipedia.org/wiki/Cycle_detection

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.

• Brent Writes Code: Huh. Never knew it had another name other than Tortoise/Hare. Learn something new every day :-D
• supercat: Wiki's description of Brent's algorithm isn't as clear as it could be. If the goal to "armor" an algorithm against cyclic behavior, a reasonable approximation of Brent's algorithm may be described as "check the second item against the first, the next two against the second, the next four against the fourth, the next eight against the eighth, etc. One major advantage of that approach is that, if one has an iterator which should yield all different elements but might erroneously fall into a cycle, Brent's algorithm will work without needing a second iterator.

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.

• R.. GitHub STOP HELPING ICE: 3 is also destructive and requires a prohibitively expensive O(n) write (exclusive) lock duration for threaded use, whereas 2 only requires a read (non-exclusive) lock.

Answer 4

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

• rlibby: No, this doesn't work. Consider A->B->B or A->B->C->B.
• Dr. belisarius: @rlibby Those are cycles. For "circular" I understand only one cycle, and all elements included in it, so tail->head.
• rlibby: @belisarius, Yes, you're right. I misread it as cyclic because circular doesn't make a lot of sense: the solution is completely trivial. I still think this is what OP meant.
• Dr. belisarius: @rlibby So I guess this one deserves upvoting for being the easiest one :D

Answer 5

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.

• AaronHS: how would you sort 4-2-6-1-5-4

Answer 6

Use the Tortoise-Hare algorithm.

• TheLoneKing: It would be more helpful if you could explain it yourself instead of just giving names and asking to search for them. This is not a place for these kind of answers.
• TheLoneKing: There is no one here who cannot Google his doubts. But I believe that this site exists not just for giving Googling suggestions. The right way to answer a question here is, I believe, to explain the answer in words. Ofcourse you can provide Googling suggestions and external links for further information about what you have explained in your answer.
• kchoi: De-duplication of answer is good, but not when it introduces a cycle. "Google brought me here" would be possible and we'll never get the actual answer. Perhaps we could detect such cases with Tortoise-Hare algorithm.

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

• Brent Writes Code: This assumes that the list circles back to the first element. What if the list was A->B->C->D->B...
• ruslik: The last node could point to any node, not necessarily to the first one.
• Asha: Yes, I assumed it is connected to the first node.

Answer 8

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

• akarnokd: Basically new HashSet(llist).size() <> llist.size() ?
• leo: No, I think this might give you a infinit loop and a crash after some time. You have realy to iterate over it.
• akarnokd: OK. It seemed that loopiness is defined by the list value itself, not the next-pointer within the list.

Answer 9

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.

• Vilx-: That will fail if the circle starts in the middle.
• Jeff Ferland: Good, but that ignores the following scenario: A->B->C->B-C->B... The loop may happen after you start. This is why the double iteration from answers above is needed.
• akarnokd: Are we talking about duplicate entries in the list?
• foobarfuzzbizz: For the most part though, circular lists are usually referring to the end being tied to the head, rather than in the middle; those are usually just referred to as cyclic.
• Bill the Lizard: samoz is right, considering the question asks specifically about circular linked-lists, not for cycles.

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

}