Program to Find Length of loop in Linked List using function | codeitwise

Here we are going to write a program to find length of loop in linked list using function. We will first create a linked list, then create a loop i.e., a cycle in the linked list and find the length of the loop.

Suppose we have a cycle or loop in a linked list as shown below then the length of the loop is 5.

Now lets implement it.

Program to Find Length of loop in Linked List using function -

C Code-

#include <stdio.h>
#include <malloc.h>

struct node{
    int data;
    struct node* next;
};

void create(struct node** head, int val);
void createcycle(struct node** head, int pos);
void detectcycle(struct node* head);
void length(struct node* nd);

void create(struct node** head, int val){
    struct node* ptr=*head;
    struct node* ptr1;
    struct node* new_node=(struct node*)malloc(sizeof(struct node));
    new_node->data=val;
    new_node->next=NULL;
    if(*head==NULL){
        *head=new_node;
        return;
    }
    while(ptr->next!=NULL){
        ptr=ptr->next;
    }
    ptr->next=new_node;
}

void createcycle(struct node** head, int pos){
    struct node* ptr=*head;
    struct node* ptr1;
    struct node* new_node=(struct node*)malloc(sizeof(struct node));
    int c=1;
    while(ptr->next!=NULL){
        if(c==pos){
            ptr1=ptr;
        }
        ptr=ptr->next;
        c=c+1;
    }
    ptr->next=ptr1;
}
void detectcycle(struct node* head){
    struct node* fast=head;
    struct node* slow=head;
    int c=0;
    while(fast!=NULL && fast->next!=NULL)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            length(slow);
            c=c+1;
            break;
        }
    }
    if (c==0){
        printf("There is no cycle in the list");
    }
}
void length(struct node* nd){
    int c=0;
    struct node *ptr=nd;
    while(ptr->next!=nd)
    {
        ptr=ptr->next;
        c++;
    }
    printf("Length of the Loop: %d",c);
}
int main(){
    struct node* head=NULL;
    create(&head,1);
    create(&head,2);
    create(&head,2);
    create(&head,4);
    create(&head,3);
    create(&head,5);
    createcycle(&head,2);
    detectcycle(head);
    return 0;
}

Output -

Length of the Loop: 4

Time Complexity: O(n) where, n=size of the linked list

Linked List Problems- 

• Count Number of Occurrence of given integer in Linked List