Best algorithm to test if a linked list has a cycle

Question

What's the best (halting) algorithm for determining if a linked list has a cycle in it?

[Edit] Analysis of asymptotic complexity for both time and space would be sweet so answers can be compared better.

[Edit] Original question was not addressing nodes with outdegree > 1, but there's some talk about it. That question is more along the lines of "Best algorithm to detect cycles in a directed graph".

Answer 1

Have two pointers iterating through the list; make one iterate through at twice the speed of the other, and compare their positions at each step. Off the top of my head, something like:

node* tortoise(begin), * hare(begin);
while(hare = hare->next)
{
    if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
    hare = hare->next;
    if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
    tortoise = tortoise->next;
}

O(n), which is as good as you can get.

Answer 2

Precondition: Keep track of the list size (update the size whenenver a node is added or deleted).

Loop detection:

1. Keep a counter when traversing the list size.

2. If the counter exceeds the list size, there is a possible cycle.

Complexity: O(n)

Note: the comparison between the counter and the list size, as well as the update operation of the list size, must be made thread-safe.

Answer 3

Take 2 pointer *p and *q , start traversing the linked list "LL" using both pointers :

1) pointer p will delete previous node each time and pointing to next node.

2) pointer q will go each time in forward direction direction only.

conditions:

1) pointer p is pointing to null and q is pointing to some node : Loop is present

2) both pointer pointing to null: no loop is there

Answer 4

You will have to visit every node to determine this. This can be done recursively. To stop you visiting already visited nodes, you need a flag to say 'already visited'. This of course doesn't give you loops. So instead of a bit flag, use a number. Start at 1. Check connected nodes and then mark these as 2 and recurse until the network is covered. If when checking nodes you encounter a node which is more than one less than the current node, then you have a cycle. The cycle length is given by the difference.

Answer 5

Two pointers are initialized at the head of list. One pointer forwards once at each step, and the other forwards twice at each step. If the faster pointer meets the slower one again, there is a loop in the list. Otherwise there is no loop if the faster one reaches the end of list.

The sample code below is implemented according to this solution. The faster pointer is pFast, and the slower one is pSlow.

bool HasLoop(ListNode* pHead)
{
    if(pHead == NULL)
        return false;


    ListNode* pSlow = pHead->m_pNext;
    if(pSlow == NULL)
        return false;


    ListNode* pFast = pSlow->m_pNext;
    while(pFast != NULL && pSlow != NULL)
    {
        if(pFast == pSlow)
            return true;


        pSlow = pSlow->m_pNext;


        pFast = pFast->m_pNext;
        if(pFast != NULL)
            pFast = pFast->m_pNext;
    }


    return false;
}

This solution is available on my blog. There is a more problem discussed in the blog: What is the entry node when there is cycle/loop in a list?

Answer 6

"Hack" solution (should work in C/C++):

• Traverse the list, and set the last bit of next pointer to 1.
• If find an element with flagged pointer -- return true and the first element of the cycle.
• Before returning, reset pointers back, though i believe dereferencing will work even with flagged pointers.

Time complexity is 2n. Looks like it doesn't use any temporal variables.

Answer 7

What about using a hash table to store the already seen nodes (you look at them in order from the start of the list)? In practise, you could achieve something close to O(N).

Otherwise, using a sorted heap instead of a hash table would achieve O(N log(N)).

Answer 8

I wonder if there's any other way than just going iteratively - populate an array as you step forwards, and check if the current node is already present in the array...

Answer 9

Konrad Rudolph's algorithm won't work if the cycle isn't pointing to the beginning. The following list will make it an infinite loop: 1->2->3->2.

DrPizza's algorithm is definitely the way to go.

Answer 10

In this case OysterD's code will be the fastest solution (vertex coloring)

That would really surprise me. My solution makes at most two passes through the list (if the last node is linked to the penultimate lode), and in the common case (no loop) will make only one pass. With no hashing, no memory allocation, etc.

Answer 11

In this case OysterD's code will be the fastest solution (vertex coloring)

That would really surprise me. My solution makes at most two passes through the list (if the last node is linked to the penultimate lode), and in the common case (no loop) will make only one pass. With no hashing, no memory allocation, etc.

Yes. I've noticed that the formulation wasn't perfect and have rephrased it. I still believe that a clever hashing might perform faster – by a hair. I believe your algorithm is the best solution, though.

Just to underline my point: the vertec coloring is used to detect cycles in dependencies by modern garbage collectors so there is a very real use case for it. They mostly use bit flags to perform the coloring.

Answer 12

This is a solution using a Hash table ( just a list actually) to save the pointer address.

def hash_cycle(node):
    hashl=[]
    while(node):
        if node in hashl:
            return True
        else:
            hashl.append(node)
            node=node.next
    return False