Find the length of a loop in the linked list

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. As we know a LinkedList allows only insertions and deletion at constant time, to get access to any random element we still need linear time. But this problem somewhat uses traversals too but in an interesting way.

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 from the same algorithm, and then we can try to think of any modifications to find its length also.

Approach #1

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

  • 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

Find 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;
}

Output: 5

Time Complexity: O(n), where n is the number of nodes.
Space complexity: 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

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

  • 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

Find the length of a loop in the linked list_2

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

Output: 5

Space complexity: O(1), no extra space is used.

So, in this blog, we have tried to explain how you can find the length of the cycle present in LinkedList. 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

Previous post Bubble Sort On Doubly Linked List
Next post Remove all occurrences of duplicates from a sorted Linked List

Leave a Reply

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