44

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?

Bill the Lizard
  • 398,270
  • 210
  • 566
  • 880
jeffD
  • 1,230
  • 3
  • 13
  • 18
  • 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. – jeffD Jan 30 '09 at 17:18

7 Answers7

47

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.

Baishampayan Ghose
  • 19,928
  • 10
  • 56
  • 60
  • Thanks, this one uses and extra Node variable though. – jeffD Jan 30 '09 at 17:11
  • 2
    Yeah, you can easily modify the above code to set fastNode1 to slowNode.next().next() :) – Baishampayan Ghose Jan 31 '09 at 07:11
  • 1
    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? – Lazer Apr 03 '10 at 02:49
  • @Lazer - there's a risk for small loops that both pointers wrap like that – Flexo Oct 07 '11 at 10:46
  • Why is the complexity o(n) ? Finding the circle is same as traversing to the last element? – ernesto Mar 27 '15 at 11:24
  • @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. – Mark Amery Sep 13 '15 at 22:03
  • 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? – Kevin Oct 29 '15 at 06:18
17

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"

Nightfirecat
  • 11,432
  • 6
  • 35
  • 51
martinus
  • 17,736
  • 15
  • 72
  • 92
  • I've sent a bug report to team@stackoverflow.com – martinus Jan 30 '09 at 08:53
  • The Wikipedia finally nails the private stupid doubt I've been having about this algorithm for years. Thanks for posting this link. –  Jan 30 '09 at 23:14
9

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
}
G S
  • 35,511
  • 22
  • 84
  • 118
  • 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 Jan 30 '09 at 08:18
  • Or on the initial assignment of fastPtr if the list is empty or 1 element long? – Lawrence Dol Jan 30 '09 at 08:22
  • 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 Jan 30 '09 at 08:42
3

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.

  • 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). – R.. GitHub STOP HELPING ICE Aug 11 '10 at 08:23
2
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;
}
rajya vardhan
  • 1,121
  • 4
  • 16
  • 29
1
boolean findCircular(Node *head)
{
    Node *slower, * faster;
    slower = head;
    faster = head->next;
    while(true) {
        if ( !faster || !faster->next)
            return false;
        else if (faster == slower || faster->next == slower)
            return true;
        else
            faster = faster->next->next;
    }
}
matias elgart
  • 1,123
  • 12
  • 18
user5297378
  • 21
  • 1
0

Taking this problem to a next step will be identifying the cycle (that is, not just that the cycle exists, but where exactly it is in the list). Tortoise and Hare algorithm can be used for the same, however, we will require to keep track of the head of the list at all times. An illustration of this algorithm can be found here.

ND_27
  • 764
  • 3
  • 8
  • 26