Introduction:

Linked lists are data structures that store data elements in a linear manner. Each element of a linked list, known as a node, consists of two parts: data and a pointer that points to the next node in the list. A linked list can have one or more loops or cycles, where a node points to a previously visited node in the list. In this article, we will discuss how to find the length of a loop in a linked list using C programming language.

Algorithm:

To find the length of a loop in a linked list, we can use the Floyd's Cycle-Finding Algorithm, also known as the Tortoise and Hare algorithm. The algorithm involves two pointers, a slow pointer (tortoise) and a fast pointer (hare), that move through the list at different speeds. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If the list has a loop, the two pointers will eventually meet at some point in the loop.

Once the two pointers meet, we can start a new pointer from the meeting point and move it along the loop until it returns to the meeting point. The number of nodes visited by this new pointer gives us the length of the loop in the linked list.

Implementation:

Let us now implement the algorithm in C programming language. We will define a linked list node structure that consists of an integer data value and a pointer to the next node in the list. We will also define a function called find_loop_length that takes a pointer to the head of the linked list as input and returns the length of the loop in the list. The implementation is as follows:

#include <stdio.h>
#include <stdlib.h>

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

// Function to find the length of the loop in the linked list
int find_loop_length(struct Node* head) {
    struct Node* tortoise = head;
    struct Node* hare = head;
    int loop_found = 0;
    int loop_length = 0;

    // Find the meeting point of the two pointers
    while (hare != NULL && hare->next != NULL) {
        tortoise = tortoise->next;
        hare = hare->next->next;
        if (tortoise == hare) {
            loop_found = 1;
            break;
        }
    }

    // If no loop is found, return 0
    if (loop_found == 0) {
        return 0;
    }

    // Find the length of the loop
    struct Node* ptr = tortoise;
    do {
        ptr = ptr->next;
        loop_length++;
    } while (ptr != tortoise);

    return loop_length;
}

// Function to create a new node in the linked list
struct Node* create_node(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->next = NULL;
    return node;
}

// Function to add a new node to the linked list
void add_node(struct Node** head, int data) {
    struct Node* node = create_node(data);
    node->next = *head;
    *head = node;
}

// Function to print the linked list
void print_list(struct Node* head) {
    struct Node* ptr = head;
    while (ptr != NULL) {
        printf("%d ", ptr->data);
        ptr = ptr->next;
    }
    printf("\n");
}

int main() {
    struct Node* head = NULL;

    // Create a linked list with a loop
    add_node(&head, 1);
    add_node(&head, 2);
    add_node(&head, 3);
    add_node(&head, 4);
    add_node(&head, 5);
    add_node(&head, 6);
    add_node(&head, 7);
    add_node(&head, 8);
    add_node(&head, 9);

struct Node* loop_start = create_node(10);
loop_start->next = head->next->next->next;
   add_node(&head, 11);
   add_node(&head, 12);
   add_node(&head, 13);
   add_node(&head, 14);
   add_node(&head, 15);
   add_node(&head, 16);
   add_node(&head, 17);
   add_node(&head, 18);
   add_node(&head, 19);
   add_node(&head, 20);

struct Node* ptr = head;
while (ptr->next != NULL) {
       ptr = ptr->next;
}
ptr->next = loop_start;

// Print the linked list
printf("Linked list: ");
print_list(head);

// Find the length of the loop in the linked list
int loop_length = find_loop_length(head);
printf("Length of the loop: %d\n", loop_length);

return 0;
}

In the main function, we create a linked list with 20 nodes and add a loop by making the next pointer of the last node point to the fourth node in the list. We then print the linked list and call the `find_loop_length` function to find the length of the loop in the list. Finally, we print the length of the loop.

Complexity:

The time complexity of the `find_loop_length` function is O(n), where n is the number of nodes in the linked list. The function first uses the Floyd's Cycle-Finding Algorithm to find the meeting point of the two pointers, which takes O(n) time in the worst case. It then uses a new pointer to traverse the loop, which takes O(k) time, where k is the length of the loop. Since k <= n, the overall time complexity is O(n).

The space complexity of the `find_loop_length` function is O(1), since it uses only constant amount of extra space for the pointers and loop variables.

Conclusion:

In this article, we have discussed how to find the length of a loop in a linked list using C programming language. We have implemented the Floyd's Cycle-Finding Algorithm to find the meeting point of two pointers in the list and then used a new pointer to traverse the loop and find its length. We have also discussed the time and space complexity of the algorithm.