Question

Modify the following code in order for it to perform the following operations:

*This code is meant to simulate Floyd's cycle finding algorithm*

A) Start with two pointers at the head of the list. We'll call the first one tortoise and the second one hare

B) Advance hare by two nodes. If this is not possible because of a null pointer, we have found the end of the list, and therefore the list is acyclic

C) Advance tortoise by one node. (A null pointer check is unnecessary. Why?)

D) If tortoise and hare point to the same node, the list is cyclic. Otherwise, go back to step 2.

C CODE:

____________________________________________________________________________________________

#include <stdio.h>

typedef struct node {
   int value;
   struct node *next;
} node;

int ll_has_cycle(node *head) {
   /* your code here */
}

void test_ll_has_cycle(void) {
   int i;
   node nodes[25]; //enough to run our tests
   for(i=0; i < sizeof(nodes)/sizeof(node); i++) {
       nodes[i].next = 0;
       nodes[i].value = 0;
   }
   nodes[0].next = &nodes[1];
   nodes[1].next = &nodes[2];
   nodes[2].next = &nodes[3];
   printf("Checking first list for cycles. There should be none, ll_has_cycle says it has %s cycle\n", ll_has_cycle(&nodes[0])?"a":"no");

   nodes[4].next = &nodes[5];
   nodes[5].next = &nodes[6];
   nodes[6].next = &nodes[7];
   nodes[7].next = &nodes[8];
   nodes[8].next = &nodes[9];
   nodes[9].next = &nodes[10];
   nodes[10].next = &nodes[4];
   printf("Checking second list for cycles. There should be a cycle, ll_has_cycle says it has %s cycle\n", ll_has_cycle(&nodes[4])?"a":"no");

   nodes[11].next = &nodes[12];
   nodes[12].next = &nodes[13];
   nodes[13].next = &nodes[14];
   nodes[14].next = &nodes[15];
   nodes[15].next = &nodes[16];
   nodes[16].next = &nodes[17];
   nodes[17].next = &nodes[14];
   printf("Checking third list for cycles. There should be a cycle, ll_has_cycle says it has %s cycle\n", ll_has_cycle(&nodes[11])?"a":"no");

   nodes[18].next = &nodes[18];
   printf("Checking fourth list for cycles. There should be a cycle, ll_has_cycle says it has %s cycle\n", ll_has_cycle(&nodes[18])?"a":"no");

   nodes[19].next = &nodes[20];
   nodes[20].next = &nodes[21];
   nodes[21].next = &nodes[22];
   nodes[22].next = &nodes[23];
   printf("Checking fifth list for cycles. There should be none, ll_has_cycle says it has %s cycle\n", ll_has_cycle(&nodes[19])?"a":"no");

   printf("Checking length-zero list for cycles. There should be none, ll_has_cycle says it has %s cycle\n", ll_has_cycle(NULL)?"a":"no");
}

int main(void) {
test_ll_has_cycle();
return 0;
}
____________________________________________________________________________________________

Answer 1

// C program to detect loop in a linked list
#include<stdio.h>
#include<stdlib.h>

/* Link list node */
struct Node
{
   int data;
   struct Node* next;
};

void push(struct Node** head_ref, int new_data)
{
   /* allocate node */
   struct Node* new_node =
       (struct Node*) malloc(sizeof(struct Node));

   /* put in the data */
   new_node->data = new_data;

   /* link the old list off the new node */
   new_node->next = (*head_ref);

   /* move the head to point to the new node */
   (*head_ref) = new_node;
}

int detectloop(struct Node *list)
{
   struct Node *slow_p = list, *fast_p = list;

   while (slow_p && fast_p && fast_p->next )
   {
       slow_p = slow_p->next;
       fast_p = fast_p->next->next;
       if (slow_p == fast_p)
       {
       printf("Found Loop");
       return 1;
       }
   }
   return 0;
}

/* Drier program to test above function*/
int main()
{
   /* Start with the empty list */
   struct Node* head = NULL;

   push(&head, 20);
   push(&head, 4);
   push(&head, 15);
   push(&head, 10);

   /* Create a loop for testing */
   head->next->next->next->next = head;
   detectloop(head);

   return 0;
}

Output:
Found loop