How to check if a Linked list is circular or not?

The only way I can think of is to traverse the link from head to tail and see if the tail links back to the head, which is O(n). That's the only way I know to get to the tail to check whether the tail is linked back to the head.

Hi CuteBug;

When creating a singly linked list you create a variable to point to the head of the list and one to point to the end of the linked list. Every time you create a new node in the list you add it to the end and adjust the tail to point to the end. The all you need is a simple if statement to see if the tail point to the head or if the tail is null see code snippet.

Fernando

public partial class Form1 : Form
{
    public Form1()
    {
        InitializeComponent();
    }
 
    private void button1_Click(object sender, EventArgs e)
    {
        SingleLinkedList head = new SingleLinkedList();
        head.Next = null;
        head.Value = 1;
        SingleLinkedList tail = new SingleLinkedList();
        head.Next = tail;
        tail.Next = null;
        tail.Value = 2;
        tail = new SingleLinkedList();
        head.Next.Next = tail;
        tail.Next = null;
        tail.Value = 3;
 
        // The tail point to nothing and therefore list is NOT circular
        if (tail.Next == null)
        {
            Console.WriteLine("List is NOT circular");
        }
 
        // Add a pointer to the head from tail.Next. This now makes the list circular.
        tail.Next = head;
        if (tail.Next == head)
        {
            Console.WriteLine("List is circular");
        }
 
       
    }
 
    public class SingleLinkedList
    {
        public SingleLinkedList Next { get; set; }
        public int Value { get; set; }
    }
}

Select allOpen in new window

Hi FernandoSoto,
    In this case i will not be creating the Linked List. Instead, I will be provided with an already created Single Linked list and I have to find whether it is circular or not.

Hi mrjoltcola,
    I agree with your answer.
   
    I had one more solution in mind -
    Have three pointers. First points to the head of the linked list. Second points to the node after the head i.e. Head.Next().
    Now the third pointer jumps twice from the head (head.Next().Next()) and then compare it with the first two pointers to know if it is circular. If it is NULL then it is not a circular list.

    I wanted to know which of the two solutions is more efficient.

regards,
CuteBug

By the way,
in my Solution, the third pointer keeps on jumping twice, until it becomes null or it matches either of the first two pointers.

Whether the pointer jumps once or twice, it is still O(n).

Normally a circular list cannot happen by accident. You can write your insert and remove function so, that it is impossible to have the same node as a predecessor *and* successor. Following that argument, there are only two ways how it could happen, either data corruption (manipulation) or the circle is wanted, i. e. the list is supposed to be circular. If  that is the case the list would contain a pointer which points to the start and end of the list.

If we assume data corruption I doubt one should make much considerations whether the detection could be recognized in O(n) or O(n^2) but how the corruption could have been possible.

> the list is supposed to be circular. If  that is the case the list would contain a pointer which points to the start and end of the list.
what is the end of a circular list?

If you know how many elements there are, the most efficient way is to run it through and see if the number of elements parsed = the number expected.

>>>> what is the end of a circular list?
Logically: the entry which points to the start node
Philosophically: anyone or none

We're assuming "circular" means that the tail points to the head but there could of course be a circular reference within the list...

The 3 pointers solution implies that we somehow know how far back the element creating the circular list points back to but we don't (at least not how the question currently stands).

As an earlier poster pointed out, it is difficult to see how this scenario could have been created by chance (or even by a coding error) so would seem to be academic exercise.

Thank you!

Just thinking about the accepted solution.

Consider:

0-->1-->2-->3-->4-->5

Where node 3 points back to node 0.

Starting at zero, the skipping pointer misses the circular dependency and hits the end of the list wrongly indicating that there is no circular reference.

Unless I'm missing something... :-(

The first pointer also moves by 1 node for each move of two nodes done by the second node. Eventually they will meet. Second node will not skip over the first node.

The non-skipping pointer will just loop round as this will hit node 3. As far as I can see they will never meet.

Regular pointer: 0,1,2,3,0...
Skipping pointer: 0,2,4...end

rd707: I didn't word it very well. The 2nd pointer doesn't have to skip, it just moves faster than the 1st pointer.

Think of a path in the woods, you and a friend are going jogging and you are faster than your friend, by say 25%. If you and your friend run long enough, you will either come to the end of the path (not circular), or you will pass your friend again (circular). Does that help?

You can't use reaching the end to indicate it is non-circular unless you wait for both pointers in which case how long do you wait?

You have to start pointer2 initially past pointer 1, or the algorithm would return immediately. If pointer2 is moving 2x as fast as pointer1, pointer2 will catch pointer1 at the end of the pointer1's first traversal of the list (if it is circular). So you don't wait very long. The point of this algorithm is it is fast, you don't use another container.

Yes, you'd have to ignore the initial case (compare to start pointer) otherwise it would always indicate a circular pointer.

The point is wherever you start the skipping pointer and whichever increment you choose there is a chance it could miss the node causing the circular reference.

You missed where I said in message 23879641, it doesn't skip, it just moves 2 nodes for every one. You compare each move. I never said skip.

I get you now - cheers.