Cyclical Linked List Algorithm

Question

I have been asked recently in a job interview to develop an algorithm that can determine whether a linked list is cyclical. As it's a linked list, we don't know its size. It's a doubly-linked list with each node having 'next' and 'previous' pointers. A node can be connected to any other node or it can be connected to itself.

The only solution that I came up at that time was to pick a node and check it with all the nodes of the linked list. The interviewer obviously didn't like the idea as it is not an optimal solution. What would be a better approach?

• AnthonyLambert: Is this the same as stackoverflow.com/questions/1442008/…
• Codism: You original solution was not a solution because if you picked up a node outside of the circle, your solution will be doing infinite loop. It's far from "optimal". Usually in an interview, a bad solution is also acceptable, if it IS a solution.
• bta: Are you wanting to check if the entire list is cyclical, or if some cycle exists inside the list?
• Carl Norum: I hate interview questions like this one. If someone knows the answer, all it tells you is that they know the answer. If they don't know the "right" answer, how are they supposed to figure it out? Blind luck? Bah. I've heard of this question being asked as "how do you find the middle node of a linked list?", which has the same solution and the same problems as an interview question. I think these have been called "Aha!" questions on past episodes of the SO podcast.
• Jonathan Leffler: I'd say this was a duplicate of SO 3001695 except that it was closed as a probable duplicate of three others: SO 2338683 and SO 494830 and SO 34249. Since SO 34249 is earliest, it 'wins'...

Answer 1

What you are looking for is a cycle-finding algorithm. The algorithm Joel refers to is called either the 'tortoise and hare' algorithm or Floyd's cycle finding algorithm. I prefer the second because it sounds like it would make a good D&D spell.

Wikpedia overview of cycle finding algorithms, with sample code

• Paul Nathan: Stepanov gives a very readable workthrough of it in his Elements of Programming.

Answer 2

The general solution is to have 2 pointers moving at different rates. They will eventually be equal if some portion of the list is circular. Something along the lines of this:

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

Blatantly stolen from here: http://ostermiller.org/find_loop_singly_linked_list.html

Answer 3

Keep a hash of pointer values. Every time you visit a node, hash its pointer and store it. If you ever visit one that already has been stored you know that your list is circular.

This is an O(n) algorithm if your hash table is constant.

• Justin K: I think it's O(n) even if your hash table auto-expands.

Answer 4

Another option is that since the list is doubly linked, you can traverse the list and check if the next pointers previous is always the current node or null and not the head. The idea here is that a loop must either encompass the entire list or look something like this:

 - -*- \
 \ \
 \---

At Node * there are 2 incoming links only one of which can be the previous.

Something like:

 bool hasCycle(Node head){
 if( head->next == head ) return true;
 Node current = head -> next;
 while( current != null && current->next != null ) {
 if( current == head || current->next->prev != current )
 return true;
 current = current->next;
 }
 return false; // since I've reached the end there can't be a cycle.
 }

• David L: +1 for the idea, but the code as written always returns true if the first two nodes are not null.
• Joel: @Dave L.: Good catch. I think this fixes it though.

Answer 5

You can handle a general complete circular list like this: Loop through the linked list via the first element until you reach the end of the list or until you get back to the first element.

But if you want to handle the case where a portion of the list is circular then you need to also move ahead your first pointer periodically.

• Mike Daniels: You will not get back to the first element if the list contains a cycle that doesn't begin at the first element.
• Brian R. Bondy: @Mike: Yes see the second part, maybe you wrote this as I was still writing.
• JohnMcG: In a one-dimensional linked list, either the whole list is a cycle, or the list does not contain cycles.
• Brian R. Bondy: @JohnMcG: Agree but I think that its not the posters intent. I think they want to detect such things as A->B->C->D->C->D->C->D->C->D...
• caf: @Brian R. Bondy: A consistent doubly-linked list can't (sensibly) contain a cycle like that, since C cannot have two previous pointers, one pointing at B and one at D.

Answer 6

Start with two pointers pointing at the same element. Walk one pointer through the list, following the next pointers. The other walks the list following the previous pointers. If the two pointers meet, then the list is circular. If you find an element with a previous or next pointer set to NULL, then you know the list is not circular.

• Mike Daniels: This does not work. The list may have a cycle somewhere in it that won't be found by this algorithm.
• Scott Langham: If you're doing this in a loop, don't move both pointers on each iteration. If you did and the number of items in the list is odd, the pointers would probably pass each other before you checked if they'd met.
• bta: @Mike Daniels- The OP was trying to detect if a list was cyclical, not whether a cycle exists inside a list (or at least that's how I read the question). @Scott Langham- Thanks, I should have clarified that point in my answer. Each iteration only moves one pointer. The reason for moving two in opposite directions is to find the end of the list (if it is not circular) faster.
• Mike Daniels: @Scott, no use trying to improve this. If I have a linked list A->B->C->D->B, and I start both pointers at A, I'm already screwed.
• JohnMcG: In one-dimensional linked list, either the whole list is a cycle, or the list doesn't contain a cycle. There's no such thing as a sub-list that's a cycle, or a node in the list that's outside the cycle. If it were graphs, then that would be different story.

Answer 7

[Edit the question and subject has been reworded to clarify that we're checking for cycles in a doubly linked list, not checking if a doubly linked list is merely circular, so parts of this post may be irrelevant.]

Its a doubly link list with each node having 'next' and 'previous' pointers.

Doubly-linked lists are commonly implemented with the head and tail of the list pointing to NULL to indicate where they end.

[Edit] As pointed out, this only checks if the list is circular as a whole, not if it has cycles in it, but that was the wording of the original question. If the list is circular, tail->next == head and/or head->prev == tail. If you don't have access to both the tail and head node and only have one of those but not both, then it should suffice to simply check if head->prev != NULL or tail->next != NULL.

If this isn't a sufficient answer because we're only given some random node [and looking for cycles anywhere in the list], then all you have to do is take this random node and keep traversing the list until you reach a node that matches (in which case it is circular) or a null pointer (in which case it's not).

However, this is essentially the same thing as the answer you already provided which the interviewer didn't like. I'm quite certain that without some magical hack, there is no way to detect a cycle in a linked list, provided a random node, without a linear complexity algorithm.

[Edit] My mind has switched gears now with the focus on detecting cycles in a list as opposed to determining if a linked list is circular.

If we have a case like: 1<->2<->3<->[2]

The only way I can see that we can detect cycles is to keep track of all the elements we traversed so far and look for any match along the way.

Of course this could be cheap. If we're allowed to modify the list nodes, we could keep a simply traversed flag with each node that we set as we're doing this. If we encounter a node with this flag already set, then we've found a cycle. However, this wouldn't work well for parallelism.

There is a solution proposed here [which I stole from another answer] called "Floyd's Cycle-Finding Algorithm". Let's take a look at it (modified to make it a little easier for me to read).

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

It basically involves using 3 iterators instead of 1. We can look at a case like: 1->2->3->4->5->6->[2] case:

First we start at [1] with a fast iterator to [2] and another at [3] or [1, 2, 3]. We stop when the first iterator matches either of the two second iterators.

We proceed with [2, 4, 5] (the first fast iterator traverses the next node of the second fast iterator, and the second fast iterator traverses the next node of the first fast iterator after that). Then [3, 6, 2], and finally [4, 3, 4].

Yay, we've found a match, and have thus determined the list to contain a cycle in 4 iterations.

• Mike Daniels: I'm almost positive the interview question was actually about detecting whether or not the list has a cycle anywhere in it, not necessarily beginning at the first element.
• Joel: This only catches the case where the entire list is circular. Usually the interviewer would prefer a full solution
• stinky472: @Joel yes, but first, I modified the post to deal with cases where the list is only partially circular and has a cycle in it. Secondly, we have to note that the OP already provided what I'd consider the correct answer for the case which is to keep traversing linearly until we find the same node or the end of the list.
• stinky472: @Joel Unless there's a faster than linear complexity solution, wouldn't the fact that the interviewer rejected this answer imply that he there's some additional contextual information about the list we can use?
• Joel: @stinky472 The OP's solution is to compare each node to every other node -- that's quadratic, not linear. If he compares only a single node, he'll miss cycles further down the list.

Answer 8

Assuming that someone says "Here a pointer to a member of a list. Is it a member of a circular list?" then you could examine all reachable members in one direction of the list for pointers to the one node that you were given a pointer to in their pointer which should point away from you. If you decide to go in the next direction then you look for next pointers that are equal to the pointer you were first given. If you choose to go in the prev direction then you look for prev pointers that equal the pointer that you were first given. If you reach a NULL pointer in either direction then you have found the end and know that it is not circular.

You could extend this by going in both directions at the same time and seeing if you bump into yourself, but it gets more complicated and it really doesn't save you anything. Even if you implemented this with 2 threads on a multi-core machine you'd be dealing with shared volatile memory comparisons, which would kill performance.

Alternately, if you can mark each node in the list you could try to determine if there was a cycle by looking for your mark while you searched for the end. If you found your mark in a node you would know that you had been there before. If you found an end before you found one of your marks you would know it wasn't circular. This would not work of another thread were trying to do this at the same time, though, because you would get your marks mixed up, but the other implementation wouldn't work if other threads were reordering the list at the same time as the test.

Answer 9

What you need is Floyd's cycle-finding algorithm. You can also think of finding the the intersection point of the cycle as homework.

Answer 10

Here is a clean approach to test if a linked list has cycles in it (if it's cyclical) based on Floyd's algorithm:

int HasCycle(Node* head)
{
 Node *p1 = head;
 Node *p2 = head;
 while (p1 && p2) { 
 p1 = p1->next;
 p2 = p2->next->next;
 if (p1 == p2)
 return 1;
 }
 return 0;
}

The idea is to use two pointers, both starting from head, that advance on different speeds. If they meet each other, that's our clue that there is a cycle in our list, if not, the list is cycle-less.

Answer 11

It is unbelievable how wide can complicated solutions spread.

Here's an absolute minimum required for finding whether a linked list is circular:

bool is_circular(node* head)
{
 node* p = head;
 while (p != nullptr) {
 p = p->next;
 if (p == head)
 return true;
 }
 return false;
}

• Joel: This is an infinite loop if the cycle starts somewhere other than the head of the list.