You’re given a linked list. The last node might point to null, or it might point to a node in the list, thus forming a cycle.
Find out whether the linked list has a cycle or not, and the length of the cycle if it does.
If there is no cycle, return 0, otherwise return the length of the cycle.
Input: Linked List: 4 -> 10 -> 3 -> 5 -> 10(at position 2)
Output: Length of cycle = 3
Explanation: The cycle is 10, 3, 5.
The first line contains an integer ‘n’, the number of elements initially in the linked list.
The next line contains ‘n’ numbers, the linked list.
The third line contains an integer ‘p’. If there is no cycle, ‘p’ = 0. Otherwise ‘p’ is the position the last node is pointing to (1 - indexed).
Return the length of the cycle, or 0 if no cycle exists.
You do not need to print anything; it has already been taken care of. Just implement the given function.
4
4 10 3 5
2
3
The cycle is 10, 3, 5.
4
4 10 3 5
0
0
Since ‘p’ = 0, the last node is pointing to null, so no cycle exists.
1 <= ‘n’ <= 100000
1 <= Data in linked list node <= 10^9
0 <= ‘p’ <= ‘n’
Floyd’s Cycle detection algorithm uses two pointers, one moving at twice of the speed of the other pointer. These fast and slow pointers meet at a common point. This common point is one of the loop nodes. If we find a common point, we can traverse the loop nodes once again to find the length of the cycle.
The steps are as follows:
int lengthOfLoop(Node * ‘head’)
O(‘n’), Where ‘n’ is the size of the linked list.
Both the loop detecting cycle and the loop calculating length will not do more than ‘n’ iterations.
Hence the time complexity is O(‘n’).
O(1)
We are not using any extra space except ‘fast’, ‘slow’ and ‘length’.
Hence the space complexity is O(1).
All tags
Sort by
Interview problems
Find length of Loop
int findlength(Node* slow, Node* fast)
{
int count =1;
fast=fast->next;
while(slow != fast)
{
count++;
fast = fast->next;
}
return count;
}
int lengthOfLoop(Node *head) {
// Write your code here
Node* slow = head;
Node* fast =head;
while(fast!=nullptr && fast->next!=nullptr)
{
slow= slow->next;
fast = fast->next->next;
if(slow == fast) return findlength(slow,fast);
}
return 0;
}
Interview problems
slow and fast pointer ( Tortoise and Hare ) Algo
int looplen(Node*t1 , Node*t2){
Node*temp1 = t1;
Node*temp2 = t2;
int cnt = 1;
while(temp2->next != temp1 ){
cnt++;
temp2= temp2->next;
}
return cnt;
}
int lengthOfLoop(Node *head) {
Node* fast = head;
Node* slow = head;
while(fast!=nullptr && fast->next != nullptr){
slow = slow->next;
fast= fast->next->next;
if(slow == fast){
return looplen(slow,fast);
}
}
return 0;
}
Interview problems
simple and easy solution
int lengthOfLoop(Node *head) {
// Write your code here
Node *slow=head;
Node *fast=head;
while(fast!=NULL && fast->next!=NULL){
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
break;
}
if(fast==NULL || fast->next==NULL)
return 0;
int count = 1;
fast = fast->next;
while(slow != fast){
count++;
fast = fast->next;
}
return count;
}
Interview problems
C++ solution using Tortoise Hare ALgorithm
int lengthOfLoop(Node *head) {
Node* fast = head;
Node* slow =head;
while(fast != NULL && fast->next != NULL){
slow = slow->next;
fast = fast->next->next;
if(slow == fast){
slow = head;
while(slow != fast){
slow = slow->next;
fast = fast->next;
}
int count = 1;
fast = slow->next;
while(slow != fast){
count++;
fast = fast->next;
}
return count;
}
}
return 0;
}
Interview problems
Find length of Loop || Optimal Approach using Floyd's Tortoise and Hare algorithm
public class Solution {
// Function to find the length of the cycle
public static int findLength(Node slow, Node fast)
{
int count = 1; // Initialize count to 1 as we're already in the cycle fast = fast.next; // Move fast pointer once
// Loop until slow and fast pointers meet again
while (slow != fast)
{
count++; // Increment count
fast = fast.next; // Move fast pointer
}
return count; // Return the length of the cycle
}
// Function to find the length of the cycle in the linked list
public static int lengthOfLoop(Node head)
{
Node slow = head; // Initialize slow pointer
Node fast = head; // Initialize fast pointer
// Traverse the list to detect a cycle
while (fast != null && fast.next != null) {
slow = slow.next; // Move slow pointer by one step
fast = fast.next.next; // Move fast pointer by two steps // If slow and fast pointers meet, it indicates a cycle if (slow == fast) {
return findLength(slow, fast); // Return the length of the cycle }
} return 0; // If no cycle is found, return 0
}
}
Interview problems
C++ Floyd's Cycle detection algo approach
/**
* Definition of linked list:
*
* class Node {
* public:
* int data;
* Node *next;
*
* Node(int data) {
* this->data = data;
* this->next = NULL;
* }
* };
*
*************************************************************************/
#include<bits/stdc++.h>
bool detectCycle(Node *head){
Node *slow = head, *fast = head;
while(fast != nullptr && fast->next != nullptr){
slow = slow->next;
fast = fast->next->next;
if(slow == fast) return true;
}
return false;
}
int lengthOfLoop(Node *head) {
// Write your code here
bool isCyclePresent = false;
Node *slow = head, *fast = head;
while(fast != nullptr && fast->next != nullptr){
slow = slow->next;
fast = fast->next->next;
if(slow == fast) {
isCyclePresent = true;
break;
}
}
int length = 0;
if(isCyclePresent){
// cout << "cycle is present\n";
// map<Node*, int> mp;
// Node *temp = head;
// int count = 0;
// //this will be infinite loop since loop is present in the list
// while(temp != NULL){
// count++;
// if(mp.find(temp) != mp.end()){
// //we have already seen this node
// return (count-mp[temp]);
// }
// mp[temp] = count;
// temp = temp->next;
// }
while(1){
fast = fast->next;
length++;
if(fast == slow) break;
}
return length;
}
return 0;
}
C++ || Using Hash Map
#include<bits/stdc++.h>
int lengthOfLoop(Node *head) {
// Write your code here
Node *temp=head;
int timer=1;
unordered_map<Node*,int> mpp;
while(temp!=NULL){
if(mpp.find(temp)!=mpp.end()){
int value=mpp[temp];
return (timer-value);
}
mpp[temp]=timer;
timer++;
temp=temp->next;
}
return 0;
}
Interview problems
java || Tortoise and Harem Algorithm
public static int lengthOfLoop(Node head) {
Node slow=head;
Node fast=head;
int cnt=0;
while(fast!=null && fast.next!=null){
slow=slow.next;
fast=fast.next.next;
if(slow==fast){
return length(slow,fast);
}
}
return 0;
}
public static int length(Node slow ,Node fast){
fast=fast.next;
int cnt=1;
while(fast!=slow){
cnt++;
fast=fast.next;
}
return cnt;
}
Interview problems
java || HashMap || normal Iteration method
public static int lengthOfLoop(Node head) {
Node temp=head;
HashMap<Node , Integer> mpp=new HashMap<>();
int timer=1;
while(temp!=null){
if(mpp.containsKey(temp)){
int value=mpp.get(temp);
return timer-value;
}
mpp.put(temp, timer);
timer++;
temp=temp.next;
}
return 0;
}
Interview problems
EASY approach solve in java
public class Solution {
public static int lengthOfLoop(Node head) {
if (head == null || head.next == null) {
return 0;
}
Node slow = head;
Node fast = head;
boolean hasLoop = false;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
hasLoop = true;
break;
}
}
if (!hasLoop) {
return 0;
}
int count = 1;
slow = slow.next;
while (slow != fast) {
count++;
slow = slow.next;
}
return count;
}
}
