detectloop.txt

来自「It is an ebook about data structures,mai」· 文本 代码 · 共 53 行

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

Discuss it!          





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