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?

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

Answer 2

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

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.