How to determine if a linked list has a cycle using only two memory locations

Question

Does anyone know of an algorithm to find if a linked list loops on itself using only two variables to traverse the list. Say you have a linked list of objects, it doesn't matter what type of object. I have a pointer to the head of the linked list in one variable and I am only given one other variable to traverse the list with.

So my plan is to compare pointer values to see if any pointers are the same. The list is of finite size but may be huge. I can set both variable to the head and then traverse the list with the other variable, always checking if it is equal to the other variable, but, if I do hit a loop I will never get out of it. I'm thinking it has to do with different rates of traversing the list and comparing pointer values. Any thoughts?

Solution 1

I would suggest using Floyd's Cycle-Finding Algorithm aka The Tortoise and the Hare Algorithm. It has O(n) complexity and I think it fits your requirements.

Example code:

function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

More info on Wikipedia: Floyd's cycle-finding algorithm.

Solution 2

You can use the Turtle and Rabbit algorithm.

Wikipedia has an explanation too, and they call it "Floyd's cycle-finding algorithm" or "Tortoise and hare"

Solution 3

Absolutely. One solution indeed can be traversing the list with both pointers, one travelling at twice the rate of the other.

Start with the 'slow' and the 'fast' pointer pointing to any location in the list. Run the traversal loop. If the 'fast' pointer at any time comes to coincide with the slow pointer, you have a circular linked list.

int *head = list.GetHead();
if (head != null) {
    int *fastPtr = head;
    int *slowPtr = head;

    bool isCircular = true;

    do 
    {
        if (fastPtr->Next == null || fastPtr->Next->Next == null) //List end found
        {
            isCircular = false;
            break;
        }

        fastPtr = fastPtr->Next->Next;
        slowPtr = slowPtr->Next;
    } while (fastPtr != slowPtr);

    //Do whatever you want with the 'isCircular' flag here
}

Solution 4

I tried to solve this myself and found a different (less efficient but still optimal) solution.

The idea is based on reversing a singly linked list in linear time. This can be done by doing two swaps at each step in iterating over the list. If q is the previous element (initially null) and p is the current, then swap(q,p->next) swap(p,q) will reverse the link and advance the two pointers at the same time. The swaps can be done using XOR to prevent having to use a third memory location.

If the list has a cycle then at one point during the iteration you will arrive at a node whose pointer has already been changed. You cannot know which node that is, but by continuing the iteration, swapping some elements twice, you arrive at the head of the list again.

By reversing the list twice, the list remains unchanged in result and you can tell if it had a cycle based on whether you arrived at the original head of the list or not.

Solution 5

int isListCircular(ListNode* head){
    if(head==NULL)
        return 0;
    ListNode *fast=head, *slow=head;
    while(fast && fast->next){
        if(fast->next->next==slow)
            return 1;
        fast=fast->next->next;
        slow=slow->next;
    }
    return 0;
}

View more solutions

Comments

[jeffD]

Thanks, the Turtle and Rabbit does give a good solution. Conceptually I also like the idea of a Rabbit looping around the Turtle if the list ever loops back on itself. BTW the list isn't expected to be a circular linked list, if it loops, it will likely point to somewhere in the middle.

[Lawrence Dol]

Won't this fail with a pointer error if fastPtr ever happens to be on the last element in the list at the top of the loop?

[Lawrence Dol]

Or on the initial assignment of fastPtr if the list is empty or 1 element long?

[martinus]

This does not work when the list does not have a cycle and the length is odd, next->next will give you a nullpointer exception (or something like that)

[martinus]

I've sent a bug report to [email protected]

[jeffD]

Thanks, this one uses and extra Node variable though.

[Admin]

The Wikipedia finally nails the private stupid doubt I've been having about this algorithm for years. Thanks for posting this link.

[Baishampayan Ghose]

Yeah, you can easily modify the above code to set fastNode1 to slowNode.next().next() :)

[Lazer]

what happens if we advance the fastNode by three at a time instead of two? Can't we detect that fastNode has crossed slowNode. Obviously the equality check (which we are currently using for detecting this) need not necessarily work with advances of three. What do you think? Wont this (hop more steps at a time) be a better algorithm?

[R.. GitHub STOP HELPING ICE]

As this requires modifying the list, I think it's a much worse solution. Two examples where it would be problematic: if the list might reside in constant memory (static const structures or a memory-mapped read-only file, for instance), or if the list is used by multiple threads (as long as access is read-only, no locking is required; with locking it would become very slow and/or stall other threads).

[Flexo]

@Lazer - there's a risk for small loops that both pointers wrap like that

[ernesto]

Why is the complexity o(n) ? Finding the circle is same as traversing to the last element?

[Unome]

Code only answers are not recommended, try to at least briefly explain what you did.

[Mark Amery]

@Lazer "Can't we detect that fastNode has crossed slowNode" - yes. "Wont this (hop more steps at a time) be a better algorithm?" - not necessarily. Consider two extreme cases. Linked list A is one big 1000000 node loop. Linked list B has a non-looping chain of 1000000 nodes that finally reaches a tiny three-node loop. Speeding up the hare will let you detect the loop in A faster (hare laps tortoise sooner), but at the cost of making you slower at detecting the loop in B (longer wait for the tortoise to even reach the loop, while the hare runs frantically in circles). It's a tradeoff.

[Kevin]

Sorry for reviving a dead question. But if we wanted to find where the loop actually began, is there a good solution to that other than tracking all the nodes we've already seen?