Cyclical Linked List Algorithm

I have been asked recently in a job interview to develop an algorithm that can determine wh开发者_开发百科ether 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?

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

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

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.

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

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.

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.

[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.

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.

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

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.

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