# Write C Program For Finding The Length Of Loop In Linked List

#### Cyber Security : Go from Zero to Hero

Most Popular

60 Lectures 5.5 hours

#### Master C and Embedded C Programming- Learn as you go

Best Seller

66 Lectures 5.5 hours

#### C Programming from scratch- Master C Programming

Best Seller

60 Lectures 8 hours

### 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>

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

// Function to find the length of the loop in the linked list
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;
}

struct Node* node = create_node(data);
}

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

int main() {

// Create a linked list with a loop

struct Node* loop_start = create_node(10);

while (ptr->next != NULL) {
ptr = ptr->next;
}
ptr->next = loop_start;

// Find the length of the loop in the linked list
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.