Thread: Detect Loop in a Linked List

How will you detect a loop in a linked list? Write a C program to detect a loop in a linked list.

Code:

/*
Start two pointers at the head of the list
  Loop infinitely
      If the fast pointer reaches a NULL pointer
        Return that the list is NULL terminated
    If the fast pointer moves onto or over the slow pointer
        Return that there is a cycle
    Advances the slow pointer one node
    Advances the fast pointer two node    
*/


#include <stdio.h>
#include <stdlib.h>

struct linkedList{
    int element;
    struct linkedList* next;
};

typedef struct linkedList* List;


/* Takes a pointer to the head of a linked list and determines
   if the list ends in a cycle or is NULL terminated
*/

int DetermineTermination(List *head)
{
    List *fast, *slow;
    fast = slow = head;
    while(1)
    {
        if(!fast || !fast->next)
            return 0;
        else if(fast == slow || fast->next == slow)
            return 1; // Loop detected
        else{
            slow = slow->next;
            fast = fast->next->next;
        }
    }
}

Do you have any better solution ??

Assuming that the loop exists in the list, the fast pointer will enter to the loop earlier followed by slow pointer. At some point, the fast pointer passes over the slow one. Based on this fact, let there is visit flat in every node which will be set by slow one upon its visit. The fast pointer needs to check the visiting node’s flag. If the flag set there will be loop otherwise the faster will reach NULL. However there will be space needed in node for this check, so for saving time we need to pay space. Also there will be one condition added in each node visit by faster pointer. Try optimizing this!

@unique

I think you got it wrong.

Please let me know if I am not making sense.

This is singly linked list, so the next pointer will point to only 1 node... so it will never go to NULL.
At some point both will have to coincide.

I am making question more clear:
You have a singly linked list, you have to detect loop in this. In the list there is a data field and a pointer to next. (You have asked to detect the loop in the list, not to change the list)

From this clarification:
- only one next pointer in each node, it will point to only one node.
- You are not going to modify the list to add a new entry flag.

Please let me know if this is not clear.