Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!
Linked list articles

Find the length of a loop in the linked list

Aniruddha Guin

In this blog, we are going to discuss the length of loop in linked list. A linked list is one of the important data structures in the technical interview because a linked list forms tricky and straightforward questions.

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

So, in this blog, we have tried to explain how you can find the length of cycle in Linked List. You can use any of these approaches, either by using a map or by using Floyd’s cycle detection algorithm although the second approach is the most efficient one and should be preferred. If you want to practice such problems check out PrepBytes – PrepBytes MyCode Contests

FAQs related to the length of loop in linked list

1. How do you find the length of a linked list?
To find the length of the linked list, we’ve to keep a counter and iterate through the linked list until the node starts pointing to null. Keep increasing the pointer at every node. The value of that pointer will be equal to the length of the linked list.

2. Is it possible to find a loop in a linked list?
Yes, we can find a loop in a linked list using Floyd’s cycle detection algorithm.

3. How would you find from which node the loop starts?
This is another variation of the above problem.

4. How do I find a loop in a list?
An easy way to detect if a linked list has a loop is through the fast runner and slow runner approach. A fast runner moves two steps at a time, while a slow runner moves one step. If there is a loop, they must collide at some point.

Leave a Reply

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

Close

Related Post