Tuesday, August 28, 2007

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;
if(!fast || !fast->next)
return 0;
else if(fast == slow || fast ->next == slow)
return 1; // Loop detected
slow = slow->next;
fast = fast->next->next;

Powered by ScribeFire.

No comments:

Post a Comment