Based on Floyd\'s algorithm for cycle detection, create an algorithm in pseudoco
ID: 3668966 • Letter: B
Question
Based on Floyd's algorithm for cycle detection, create an algorithm in pseudocode that breaks a linked list into two sub-lists:
X- The part of the list from beggining to before the connecting point
Y- The part of the list closing into a loop starting at the connecting point
Note: the algorithm should still work even if the list does not contain a loop (we would have X = whole list and Y = empty)
Then, analyse the running time of the algorithm as a function of the number of cells in the list. How much space does it use as a function of the number of cells ?
Explanation / Answer
// 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;
}
Time Complexity: O(n)
Auxiliary Space: O(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;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.