Find Length of Loop of the Linked List

Find Length of Loop of the Linked List” problem is an extension of problem “Detect Loop in a Linked List. In this problem, we need to detect loop whether loop exists in a linked list or not, and if loop exists, then we need to find the length of loop of the linked list. In simpler language, we need to count how many nodes are there which are in the loop.

Now, to find the length of the loop of the linked list, firstly, we need to detect whether a loop exist in a linked list or not. If loop exist in the linked list, we need to traverse the entire loop to count the number of nodes in a loop.

For example, in the below linked list, the loop length of loop present in the linked list 3. Nodes with values {2}, {3} and {4} are forming the loop in the below case.

Linked List with Loop of length ‘3’

The steps required to find the length of the loop is as follows:

  1. The very initial step to find the length of loop of the linked list is to check whether loop exists in the linked list or not. To detect whether loop exists in the linked list or not, we have discussed two methods; hashing based and Floyd’s loop detection algorithm. Using any one of these two method, we can detect whether loop exists in the linked list or not.
  2. If the Loop does not exists in the linked list, then the length of the loop of the linked list will be zero.
  3. If the Loop exists in the linked list, we will traverse the whole loop and count the number of nodes present in the linked list.
  4. Finally, we will print the count.

C++ Program to find length of the loop in a linked list is as follows:

/* C++ Program to find the length of the loop of the linked list */
#include<bits/stdc++.h>
using namespace std;

/* Strcuture of the Node of the Linked List */
struct node
{
    int data;
    struct node *next;
};

/* Function to insert node at the end of the linked list */
void insert_end(struct node **head, int ele)
{
    /* Creating a new node */
    struct node *new_node;
    new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = ele;
    new_node->next = NULL;
    
    /* check whether the linked list is empty or not */
    
    /* If Linked List is empty, new node will become head of the linked list */
    if(*head == NULL)   
    {
        *head = new_node;
        return;
    }
    
    /* If Linked List is not empty, traverse the complete linked list and point the pointer 
    of last node of the linked list to the new node*/
    struct node *temp = NULL;
    temp = (*head);
    while(temp->next != NULL)
    temp=temp->next;
    temp->next = new_node;
}

/* A Utility function to create Loop in a Linked List */
void create_loop(struct node **head)
{
    struct node *temp = (*head);
    while(temp->next !=NULL)
    temp = temp->next;
    temp->next = (*head)->next;
}

/* Function to detect loop in a linked list and if loop exists, find the length of the loop */
int detectLoopLength(struct node *head)
{
    /* Initialize two pointers; slow pointer which will traverse the linked list one node
    at a time and fast pointer which will traverse the linked list two nodes at a time */
    struct node *slow = head;
    struct node *fast = head;
    while(slow!=NULL && fast!=NULL && fast->next!=NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
        /* If at any time, the slow pointer and faster pointer meets, 
        then there exists a loop in the linked list  */
        if(slow == fast) 
        {
            /* Now, traverse the complete loop and count the number of nodes present
            in the loop to find the length of the loop of the linked list */
            struct node *temp = slow;
            int len = 1;
               while(temp->next != slow) 
            {
                len++;
                temp = temp -> next;       
            }        
            return len;
        }
    }
    /* If loop does not exists, we will return loop length as zero */
    return 0;
}
int main()
{
    struct node *head;
    head = NULL;
    /* Insert Some Nodes in the Linked List */
    insert_end(&head,4);
    insert_end(&head,3);
    insert_end(&head,2);
    insert_end(&head,1);
    /* Calling a utility function to create Loop in the Linked List */
    create_loop(&head);
    
    /* Calling detectLoopLength function to find the length of the loop of the linked list */
    int len = detectLoopLength(head);
    /* Printing the result */
    cout<<"Length of loop present in the linked list is: "<<len;
}
OUTPUT:
Length of loop present in the linked list is: 3

Related Posts:

  1. Detect a Loop in a Linked List.
  1. Detect and Remove Loop from a Linked List.
  2. Detect a Loop in a Linked List.
  3. Segregate Even and Odd Nodes of the Linked List.
  4. Delete Complete Linked List.
  5. Delete Nth Node of the Linked List.
  6. Delete without head pointer of the Linked List.
  7. Delete All Occurrences of particular node of the Linked List.
  8. Delete Alternate Nodes of the Linked List.
  9. Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.
  10. Remove Duplicate Nodes from an Unsorted Linked List.
  11. Remove Duplicate Nodes from a Sorted Linked List.
  12. Find Union and Intersection of Two Linked List.
  13. Merge Two Sorted Linked List.
  14. Insert a New Node at the Sorted Linked List.
  15. Reverse a Linked List.
  16. Reverse a Linked List Using Stack.
  17. Printing Linked List in Reverse Order without actually reversing the Linked List.
  18. Swap Adjacent Elements of the Linked List.
  19. Count All Occurrences of a Particular Node in a Linked List.
  20. Bubble Sort on Linked List.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *