Suppose that you are given a linked list that is either circular or or not circular (another word for not circular is acyclic). Take a look at the figures below if you are not sure what a circular linked list looks like.
Write a function that takes as an input a pointer to the head of a linked list and determines whether the list is circular or if the list has an ending node. If the linked list is circular then your function should return true, otherwise your function should return false if the linked list is not circular. You can not modify the linked list in any way.
This is an acyclic (noncircular) linked list:
This is a circular linked list:
You should start out this problem by taking a close look at the pictures of a circular linked list and a singly linked list so that you can understand the difference between the 2 types of lists.
The difference between the 2 types of linked lists is at the very last node of the list. In the circular linked list, you can see that the very last node (37) links right back to the first node in the list – which makes it circular. However, in the acyclic or noncircular linked list you can see that the end node does not point to another node in the linked list and just ends.
It is easy enough to know when you are in an acyclic linked list – the pointer in the end node will just be pointing to NULL. However, knowing when you are in a circularly linked list is more difficult because there is no end node, so your function would wind up in an infinite loop if it just searches for an end node. So, there has to be a solution other than just looking for a node that points to NULL, since that clearly will not work.

Take a closer look at the end node (37) in the circular linked list. Note that it points to the head node (12), and that there must also be a head pointer that points to the head node. This means that 12 is the only node that has 2 pointers pointing to it. And, suppose 37 pointed to 99, then this would still be a circularly linked list, and 99 would be the only node that has 2 pointers pointing to it. So, clearly, in a circular linked list there will always be a node that has 2 pointers pointing to it. Now the question is whether we can use that property to somehow provide a solution to this problem – by traversing the list and checking every node to determine whether 2 nodes are pointing at it? If true, the list is circular. If not true, the list is acyclic and you will eventually run into a NULL pointer at the last element.
Too difficult a solution to find if a linked list is cyclical
This sounds like a good solution, but unfortunately it is difficult to find out how many pointers each element has pointing to it. So, before we even try to implement this solution, we should eliminate it since it will be very messy and difficult to implement.
Another way of looking at a circular linked list is to say that if you are traversing the list and you have visited the same node twice, then you know that the linked list is circular. So, another possible algorithm is this: if we have already encountered a node, then we know the linked list is circular, but if we encounter a NULL pointer then we know that the linked list is acyclic. But, the big question here is how do we determine whether or not we have already visited a node in an algorithm?
One way of doing this would be to mark each node after visiting it and then check to see if a node that you are visiting already has a mark. But, we can not modify the list in any way. Another option is to put all the nodes that we have already visited in a separate data structure, and then we would compare the current node to all of the nodes in that separate data structure. If we have a match, then we know that we are in a circular linked list. This would definitely work, but in the worst casescenario (where the last node points to the head node) it would require as much memory as the linked list that you are given. Can we somehow minimize the memory requirement?

Well, why bother replicating the linked list we are given, when we can just use the linked list itself to compare to. All we have to do is compare the current node’s pointer to the previous nodes directly. So, for the nth node, we just compare its next pointer to see if it points to any nodes from 1 to n – 1. If any of those nodes are equal then we know that we have a circular linked list.
Let’s figure out what the BigO is of our algorithm is (for a refresher on BigO Notation read this:Big O Notation Explained). If we are at the first node, then we examine 0 nodes; if we are at the 2nd node then 1 node is examined, if we are at the 3rd node then 2 nodes are examined. This means that the algorithm examines 0 + 1 + 2 + 3 + …. + n nodes. The sum of 0 + 1 + 2 +…+ n is equal to (n^{2})/2 + n/2. And when calculating the BigO of an algorithm we take off everything except the highest order term, so this means our algorithm is O(n^{2}).
Try using 2 pointers to find if linked list is cyclic
Can we do better than this solution? Well, yes there is a better solution – although it is very difficult to have come up with unless you were given some sort of hint. Suppose we had 2 pointers instead of just one. Then what we could do is advance the pointers at different speeds.
What happens if we advance 2 pointers at different speeds – so that one pointer is traversing the list faster than the other pointer? So, we can have one slower pointer just going through every item in the linked list, and the other faster pointer traversing every other item in the linked list. In an acyclic (noncircular) list, the faster pointer will eventually hit a null pointer. But in a circular list, the faster pointer will eventually catch up to the slower pointer because the pointers are going in a circle. Take a few seconds and think about that to make sure it makes sense to you – just imagine 2 pointers going in a circle, one faster and one slower. The faster one will eventually catch up to the slower one if it’s moving at twice the speed. Or, imagine two runners on a small circular jogging track – the faster runner will eventually cross the slower jogger again, and be one lap ahead (assuming of course that they jog log enough for this to happen) of the slower jogger. So, this is another solution, and here is the pseudocode for this problem:
2 pointers travelling at different speeds start from the head of the linked list Iterate through a loop If the faster pointer reaches a NULL pointer then return saying that the list is acyclic and not circular If the faster pointer is ever equal to the slower pointer or the faster pointer's next pointer is ever equal to the slower pointer then return that the list is circular Advance the slower pointer one node Advance the faster pointer by 2 nodes
Solution to finding if linked list is circular using tortoise and hare algorithm
The algorithm that we gave the pseudocode for above is actually known as the tortoise and hare algorithm – where the faster pointer is considered the “hare” (which is a rabbit, for those of you who learned English as a second language), and the slower pointer is considered the tortoise.
If we write the actual code for this, it would look like this:
bool findCircular(Node *head) { Node *slower, * faster; slower = head; faster = head>next; //start faster one node ahead while(true) { // if the faster pointer encounters a NULL element if( !faster  !faster>next) return false; //if faster pointer ever equals slower or faster's next //pointer is ever equal to slow then it's a circular list else if (faster == slower  faster>next == slower) return true; else{ // advance the pointers slower = slower>next; faster = faster>next>next; } } }
The Big O of solution to find if linked list is circular
And there is our solution. What is the BigO of our solution? Well, what’s the worst case if we know that the list is circular? In this case, the slower pointer will never go around any loop more than once – so it will examine a maximum of n nodes. The faster pointer, however, will traverse through 2n nodes and examine half of those nodes (n nodes). The faster pointer will pass the slower pointer regardless of the size of the circle – which makes it a worse case of n +n, which equals 2n nodes. This is O(n).
The Big O of the worst case when list is acyclic
And what about the worst case when the list is not circular – acyclic? Then the faster pointer will have come to the end after traversing through n nodes and examining n/2 nodes since the faster pointer skips every other node. The slower pointer will have examined n/2 nodes, which means that combined the faster and slower pointer will have examined n/2 + n/2 nodes, which is also O(n). Thus, the algorithm is O(n) for both worst case scenarios.
I know the reason. We could let the faster pointer move two steps and slower one move step, then in the worst case is O(2n)~=O(n).
In the case of circular, why “the slower pointer will never go around any loop more than once – so it will examine a maximum of n nodes”? I mean the time when the faster pointer hit the slower one depends on the (circumference/(FastSpeedSlowSpeed)). So how do you control the speed of the faster pointer and the slower one in the program? Could you give me a code to explain that? Much thanks
What if their are two equal nodes in the linkedlist
How do i compare the current’s node pointer to the previous nodes?
How do i compare it with each and every node?
As has been mentioned in other comments, the cycle doesn’t necessarily contain the head/start node. The cycle could be as simple as the last node pointing back at the secondtolast node.
For example, A>B>C>B>C>B>C…
In your solution, ptr would always point at A, and ptr1 would end up cycling forever between B and C.
Isn’t this a two pointer model?
You can find out the cycle or loop in a single linked list by using two pointer approach.
Below link can be useful to find out the algorithm to find cycle or loop in linked list
Find out loop or cycle in linked list in java
http://newtechnobuzzz.blogspot.in/2014/07/howtofindloopsorcyclesinlinked.html
The walk may not necessarily circle back to the ‘head’. For example in the diagram at the top of the page (12>99>37), 37 may not necessarily point back to 12 (which is the ‘head’). Instead, 37 could point to 99 causing it to be circular without ever passing through ‘head’ again.
I have a different solution please let me know if it proper.
ptr=start;
ptr1=start>next;
while(ptr1)
{
if (ptr==ptr1)
{
print(“circular”);
break;
}
ptr1=ptr1>next;
}
Here is my solution on the same (from http://k2code.blogspot.in/2011/12/findingstartofloopincircular.html) :
/**
* Returns the node at the start of a loop in the given circular linked
* list. A circular list is one in which a node’s next pointer points
* to an earlier node, so as to make a loop in the linked list. For
* instance:
*
* input: A > B > C > D > E > C [the same C as earlier]
* output: C
*
*
* @param linkedList
* list to be tested
* @return the node at the start of the loop if there is a loop, null
* otherwise
*/
public static IntegerNode findLoopStart(LinkedList linkedList) {
if (linkedList == null  linkedList.getHead() == null) {
return null;
}
IntegerNode loopStartNode = null;
IntegerNode slow = linkedList.getHead();
IntegerNode fast = linkedList.getHead();
while (slow != null && fast != null) {
slow = slow.getNext();
if (fast.getNext() == null) {
loopStartNode = null;
break;
}
fast = fast.getNext().getNext();
// If slow and fast point to the same node, it means that the
// linkedList contains a loop.
if (slow == fast) {
slow = linkedList.getHead();
while (slow != fast) {
// Keep incrementing the two pointers until they both
// meet again. When this happens, both the pointers will
// point to the beginning of the loop
slow = slow.getNext(); // Can’t be null, as we have a loop
fast = fast.getNext(); // Can’t be null, as we have a loop
}
loopStartNode = slow;
break;
}
}
return loopStartNode;
}
faster>next == null check was already done in the first if.
then when you set faster to be faster>next>next, if that one is null it will be caught in the same null check (first if).
Sorry your code “faster = faster>next>next;” might cause null pointer error. Think about when faster>next == null, what would happen?
Update: Ok I understand the scenario, the scenario being a linked list with a loop.In that case we cannot have one static pointer. The following website was helpful,
http://umairsaeed.com/2011/06/23/findingthestartofaloopinacircularlinkedlist/
Thanks Artem for helping me think in a different perspective.
If i understand your list structure correctly. in that case the list will not be circular or will not work. For instance, consider you are given a pointer A* which points to cell 6 and the last cell points to cell 5. if we have to find the item in cell 1 according to the list structure you specified the program will be locked in an infinite loop from cell 5 to last cell and will not be able to find the item in cell 1.
we cannot because circular linked list doesn't mean that last node is connected to the first node. It may be connected to the 5th node for example. Then u will get an infinite loop.
why dont you compare memory address of head for circular linked list.
This won't work if the loop starts later in the list. e.g. "last element" goes back to 3rd element in list.
why do we need both the pointers to be traversing the list to find whether the list is circular? Instead, we can have one pointer fixed on one of the node and the next pointer to traverse from the next node on, and compare if the next address is the same as the fixed pointer address.
If you do not start faster = head>next, then the condition (faster==slower) would always be true at the beginning of the loop.
"Additionally we would just need to check "faster == slower" instead of "faster == slower  faster>next == slower"." This one I agree.
Also, I think it is not really necessary to move the slower pointer. We may just define a "stand = head>next" at the beginning and hold it unchanged. Then start the loop checking whether a moving pointer reaches the stand (faster==stand) then we know it's a circular.
Same example, two runners on a circular track, one stands still, and the other runs. When two meet each other, then we know it's a circular. This is faster than both running in the track.
Thanks!!
Awesome… I liked this post very much.. Really appreciate.