Write a C program that will determine whether or not a given singly-linked list

Question

Write a C program that will determine whether or not a given singly-linked list structure contains a loop. The program must always terminate; in other words, if there is a loop it must determine this and print this result in a finite amount of time. Assume that you start from a pointer to the head of the list and that the end of the list is marked by having a NULL pointer in the next-element pointer field. You cannot make any assumptions about how big the potential loop is or where it might be in the data structure. You should test you problem with both a normal linked list and one containing a loop.

Explanation / Answer

#include #include /* Link list node */ struct node { int data; struct node* next; }; void push(struct node** head_ref, int new_data) { struct node* new_node = (struct node*) malloc(sizeof(struct node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } // returns 1 if loop found,else 0 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) { return 1; } } return 0; } int main() { /* create list */ struct node* head = NULL; push(&head, 20); push(&head, 4); push(&head, 15); push(&head, 10); /* test list without loop */ if( detectloop(head)==1) printf("Loop Found "); else printf("No Loop Found "); /* Create a loop for testing */ head->next->next->next->next = head; /* test list again with loop */ if( detectloop(head)==1) printf("Loop Found "); else printf("No Loop Found "); return 0; }

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.