Detect a loop in a linked list

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


/*
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;
}
}
}

Powered by ScribeFire.