Find the length of a loop in the linked list

Last Updated on November 27, 2023 by Ankit Kochar

In the realm of data structures, linked lists are foundational, offering dynamic memory allocation and efficient data manipulation. However, linked lists can occasionally contain loops or cycles, which disrupt their linear structure. Determining the length of a loop within a linked list poses an intriguing challenge for developers and requires a nuanced understanding of algorithms and pointer manipulation. This article aims to explore methodologies and algorithms to find the length of a loop within a linked list, elucidating step-by-step approaches to solve this common problem in data structure manipulation.

How to find the length of loop in linked list

In this problem, we are given a LinkedList (root node) and are asked to find the length of the cycle/loop that is present in the LinkedList. Let me explain this with an example:-

The above-Linked List has a loop that has 6 nodes in the loop/cycle. Hence, this shall return 6 as the answer.
Well, the very first task that I can observe is to determine whether the LinkedList contains a cycle or not. So, it shall follow the same algorithm, and then we can try to think of any modifications to find its length also.

Approach #1 to find the length of loop in linked list

The first approach is based on maps. The idea is to store the address of the nodes as the key and their position as the values. So, when we traverse and insert into the map if we come across a node that points to an address that is already present in the map that means there is a cycle present in the LinkedList. From this, we can find the length by simply subtracting the current position from the position of the matched node as position - map[currnode].

Algorithm to find the length of loop in linked list

• Start traversing every node of the linked list present and maintain the position(incremented with every node) in the map.
• While inserting also check if that node is present in the map, that will mean we have come across that node and there is a cycle cause we are visiting the node again.
  • If the node is not present in the map – increment the position counter and insert the current node address in the map.
  • If the node is present in the map – then there is a cycle and we can find the number of nodes from position - map[currnode]

Code Implementation to find the length of loop in linked list

#include 
using namespace std;
struct Node {
    int data;
    struct Node* next;

    Node(int num)
    {
        data = num;
        next = NULL;
    }
};
int countNodesinLoop(struct Node* head)
{
    struct Node* p = head;
    int pos = 0;
    unordered_map m;
    while (p != NULL) {
        if (m.find(p) == m.end()) {
            m[p] = pos;
            pos++;
        }
        else {
            return (pos - m[p]);
        }
        p = p->next;
    }
    return 0;
}
int main()
{
    struct Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5); 
    head->next->next->next->next->next = new Node(6); 
    head->next->next->next->next->next->next = head->next;
    cout << countNodesinLoop(head) << endl; 
    return 0;
}

class Node:
	def __init__(self, val):
		self.val = val
		self.next = None
	
class LinkedList:
	
	def __init__(self):
		self.head = None	

	def AddNode(self, val):
		if self.head is None:
			self.head = Node(val)
		else:
			curr = self.head
			while(curr.next):
				curr = curr.next
			curr.next = Node(val)

	def countNodesinLoop(self):
		
		p = self.head
		pos = 0
		m = dict()

		while p:
			
			if p not in m:
				m[p] = pos
				pos += 1

			else:
				return pos - m[p]

			p = p.next

		return 0
	
myLL = LinkedList()
myLL.AddNode(1)
myLL.AddNode(2)
myLL.AddNode(3)
myLL.AddNode(4)
myLL.AddNode(5)
myLL.AddNode(6)

myLL.head.next.next.next.next.next.next = myLL.head.next
loopLength = myLL.countNodesinLoop()
if myLL.head is None:
	print("Linked list is empty")
else:
	print(str(loopLength))

Output: 5

Time Complexity of the length of loop in linked list: O(n), where n is the number of nodes.
Space complexity of the length of loop in linked list: O(n), for using a map

As you can see, this method uses some extra space, we have to try to think of something better to reduce the extra space at least.

Approach #2 to find the length of loop in linked list

The next idea is based on Floyd’s Cycle detection algorithm. The concept is to use two pointers, one fast-moving another slow-moving. Both the pointers traverse the linked list with different speeds and when they meet each other that means there’s a cycle present in the LinkedList. Save the address of this node and take a counter with 1 and start incrementing it while traversing the LinkedList again from the common point with another pointer. Once we reach the common pointer again, then we will have our number of nodes in cycle count in the pointer. We will return this count.

Algorithm to find length of loop in linked list

• Take two pointers, a fast pointer, and a slow pointer pointing to the head initially.
• Traverse both the pointers as slowptr = slowptr->next (1 node at a time), and fastptr = fastptr->next->next (2 nodes at a time).
• When slowptr == fastptr, the common point is the node for the head of the cycle.
• Fix one pointer to this node and take count = 0 and move the other pointer from the common point one by one in the linked list and increment the counter by 1 in each step
• When the other pointer reaches the common point then stop the iteration and return the count.

Code Implementation to find length of loop in linked list

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

struct Node
{
    int data;
    struct Node* next;
};
int countNodes(struct Node *n)
{
    int res = 1;
    struct Node *temp = n;
    while (temp->next != n)
    {
        res++;
        temp = temp->next;
    }
    return res;
}
int countNodesinLoop(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 countNodes(slow_p);
    }
    return 0;
}
struct Node* newNode(int x)
{
    struct Node* node = malloc(sizeof(struct Node*));
    node->data = x;
    node->next = NULL;
    return node;
}
int main()
{
    struct Node *head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);
    head->next->next->next->next->next = newNode(6); 
     head->next->next->next->next->next->next = head->next;
     int ans = countNodesinLoop(head);
     printf("%d \n",ans);
    return 0;
}

#include
using namespace std;

struct Node
{
    int data;
    struct Node* next;
};
int countNodes(struct Node *n)
{
    int res = 1;
    struct Node *temp = n;
    while (temp->next != n)
    {
        res++;
        temp = temp->next;
    }
    return res;
}
int countNodesinLoop(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 countNodes(slow_p);
    }
    return 0;
}

struct Node *newNode(int key)
{
    struct Node *temp = new Node();
    temp->data = key;
    temp->next = NULL;
    return temp;
}
int main()
{
    struct Node *head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);
    head->next->next->next->next->next = new Node(6); 
     head->next->next->next->next->next->next = head->next;
    cout << countNodesinLoop(head) << endl;
    return 0;
}

class LoopI 
{
	
    static class Node
    {
	    int data;
	    Node next;
	    Node(int data)
	    {
		    this.data =data;
		    next =null;
	    }
    }
    static int countNodes( Node n)
    {
        int res = 1;
        Node temp = n;
        while (temp.next != n)
        {
	        res++;
	        temp = temp.next;
        }
        return res;
    }
    static int countNodesinLoop( Node list)
    {
	    Node slow_p = list, fast_p = list;
        while (slow_p !=null && fast_p!=null && fast_p.next!=null)
	    {
		    slow_p = slow_p.next;
		    fast_p = fast_p.next.next;

		    if (slow_p == fast_p)
			    return countNodes(slow_p);
	    }
        return 0;
    }
    static Node newNode(int key)
    {
	    Node temp = new Node(key);
	
	    return temp;
    }
	public static void main (String[] args) 
    {
		Node head = newNode(1);
	    head.next = newNode(2);
	    head.next.next = newNode(3);
	    head.next.next.next = newNode(4);
	    head.next.next.next.next = newNode(5);

	    /* Create a loop for testing */
	    head.next.next.next.next.next = head.next;

	    System.out.println( countNodesinLoop(head));
	}
}

class Node:
	def __init__(self, val):
		self.val = val
		self.next = None
	
class LinkedList:
	
	def __init__(self):
		self.head = None	

	def AddNode(self, val):
		if self.head is None:
			self.head = Node(val)
		else:
			curr = self.head
			while(curr.next):
				curr = curr.next
			curr.next = Node(val)

	def countNodesinLoop(self):
		
		if self.head is None:
			return 0
		
		slow = self.head
		fast = self.head
		flag = 0 

		while(slow and slow.next and fast and
			fast.next and fast.next.next):
			if slow == fast and flag != 0:
				count = 1
				slow = slow.next
				while(slow != fast):
					slow = slow.next
					count += 1
				return count
			
			slow = slow.next
			fast = fast.next.next
			flag = 1
		return 0 
	
myLL = LinkedList()
myLL.AddNode(1)
myLL.AddNode(2)
myLL.AddNode(3)
myLL.AddNode(4)
myLL.AddNode(5)
myLL.AddNode(6)

myLL.head.next.next.next.next.next.next = myLL.head.next
loopLength = myLL.countNodesinLoop()
if myLL.head is None:
	print("Linked list is empty")
else:
	print(str(loopLength))

Output: 5

Space complexity to find length of cycle in linked list: O(1), no extra space is used.

Conclusion
Identifying and determining the length of a loop within a linked list demands a deep understanding of pointer manipulation and algorithmic techniques. Various methods, such as Floyd’s Cycle Detection Algorithm or using additional data structures, enable programmers to detect loops and calculate their lengths effectively. This knowledge proves invaluable in maintaining the integrity of linked list operations, enhancing algorithm efficiency, and ensuring robustness in data structure manipulation. By mastering these techniques, programmers can adeptly navigate and manage linked lists containing loops, enabling the development of more resilient and optimized software systems.

FAQs related to the length of loop in linked list

Here are some FAQs related to the Length of Loop in Linked List.

1. What is a loop in a linked list?
A loop in a linked list refers to a scenario where a node within the list, rather than pointing to the next node in sequence, points to a node that is earlier in the list, creating a cycle or loop within the structure.

2. How do you detect the presence of a loop in a linked list?
Several algorithms, such as Floyd’s Cycle Detection Algorithm (also known as the "Tortoise and Hare" algorithm), can be employed to detect the presence of a loop in a linked list. By using two pointers moving at different speeds through the list, this algorithm can identify if and where the pointers meet, indicating the existence of a loop.

3. How can you find the length of a loop in a linked list?
Once a loop is detected within a linked list, determining its length involves intricate pointer manipulation. One approach involves using the meeting point of the pointers (found using Floyd’s algorithm) as a reference to traverse the loop, counting the number of nodes until the pointers meet again to calculate the loop’s length.

4. Are there other methods to find the length of a loop?
Alternative methods to find the length of a loop in a linked list include utilizing a hash table to store visited nodes or modifying the data structure by introducing additional pointers or attributes to mark and count nodes while detecting loops.

5. Why is determining the length of a loop important in linked list manipulation?
Understanding the length of a loop in a linked list is crucial for various applications, including memory management, algorithmic optimizations, and ensuring the integrity of linked list operations. It aids in designing algorithms that handle cyclic structures efficiently and accurately.