English flagEnglish  
CLOSE

Suggested:

🛠️ Settings

Problem Statement

Given a linked that may contain a loop, we need to find the length of the loop. A loop in a linked list occurs when a node's next pointer points to a previously visited node in the list, creating a cycle. The task is to detect this loop and determine its length.

Examples

Example 1:

Input: Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
                                             ↑         ↓
                                            12 <- 11 <-10
Output: 6

Explanation: Node 12 points back to node 6, creating a loop of length 6.
Example 2:

Input: Linked List = 1 -> 3 -> 7 -> 4
Output: 0

Explanation: No loop is present in the linked list.
Example 3:

Input: Linked List: 6 -> 3 -> 7
                    ^         |
                    |         |
                    +---------+

Different Approaches

1️⃣ Hashing

Intuition:

One way to approach this problem is by utilizing hashing. We can traverse the linked list, keeping track of visited nodes using a hash table or unordered set. If a node is encountered again during traversal, it indicates the presence of a loop. By storing visited nodes in a hash table, we can quickly check if a node has been visited before.

Algorithm:

  1. Initialize an unordered set/hash table to store visited nodes.
  2. Traverse the linked list.
  3. For each node encountered:
    1. If the node's address is already present in the set, a loop is detected.
    2. Otherwise, insert the node's address into the set.
  4. If a loop is detected, traverse it again to count its length.
  5. Return the length of the loop.

Code:

#include <iostream>
#include <unordered_set>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

int lengthOfLoop(ListNode *head) {
    unordered_set<ListNode*> visited;
    ListNode *current = head;

    while (current != nullptr) {
        // If the current node is already visited, it indicates a loop
        if (visited.find(current) != visited.end()) {
            int length = 1;
            ListNode *temp = current->next;
            // Count the length of the loop
            while (temp != current) {
                length++;
                temp = temp->next;
            }
            return length;
        }

        // Mark the current node as visited
        visited.insert(current);
        current = current->next;
    }

    // No loop found
    return 0;
}

int main() {
    ListNode *head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    head->next->next->next->next->next = head->next; // Create loop

    cout << "Length of loop: " << lengthOfLoop(head) << endl;

    return 0;
}
OR:
#include <bits/stdc++.h>

using namespace std;

// Definition of singly linked list:
struct ListNode
{
    int val;
    ListNode *next;
    ListNode()
    {
        val = 0;
        next = NULL;
    }
    ListNode(int data1)
    {
        val = data1;
        next = NULL;
    }
    ListNode(int data1, ListNode *next1)
    {
        val = data1;
        next = next1;
    }
};

class Solution {
public:
    // Function to find length
    int findLengthOfLoop(ListNode *head) {
        // Hashmap to store visited nodes and their timer values
        unordered_map<ListNode*, int> visitedNodes;

        // Initialize pointer to traverse the linked list
        ListNode* temp = head;

        // Initialize timer 
        // to track visited nodes
        int timer = 0;

        // Traverse the linked list 
        // till temp reaches nullptr
        while (temp != NULL) {
            // If revisiting a node return difference of timer values
            if (visitedNodes.find(temp) != visitedNodes.end()) {
                // Calculate the length of the loop
                int loopLength = timer - visitedNodes[temp];

                // Return length of loop
                return loopLength;
            }
            /* Store the current node 
            and its timer value in 
            the hashmap */
            visitedNodes[temp] = timer;

            // Move to the next node
            temp = temp->next;

            // Increment the timer
            timer++;
        }

        /** If traversal is completed 
         * and we reach the end 
         * of the list (null)
         * means there is no loop */
        return 0;
    }
};

int main() {
    // Create a sample linked list with a loop
    ListNode* head = new ListNode(1);
    ListNode* second = new ListNode(2);
    ListNode* third = new ListNode(3);
    ListNode* fourth = new ListNode(4);
    ListNode* fifth = new ListNode(5);

    // Create a loop from fifth to second
    head->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = fifth;

    // This creates a loop
    fifth->next = second;

    Solution solution;
    int loopLength = solution.findLengthOfLoop(head);
    if (loopLength > 0) {
        cout << "Length of the loop: " << loopLength << endl;
    } else {
        cout << "No loop found in the linked list." << endl;
    }

    return 0;
}

Complexity Analysis:

  • Time Complexity: O(n)
    • Because the code traverses the entire linked list at least once, where n is the number of nodes in the list.
  • Space Complexity: O(n)
    • Because the code uses a hashmap to store encountered nodes, which can take up to O(n) additional space, where n is the number of nodes in the list.

2️⃣ Floyd's Cycle Detection Algorithm (Hare and Tortoise):

Detecting a loop in a linked list can be done using Floyd's Cycle Detection Algorithm, also known as the tortoise and hare algorithm. This algorithm involves using two pointers: one slow pointer that moves one step at a time and a fast pointer that moves two steps at a time. If there is a loop, eventually the fast pointer will catch up to the slow pointer. The point where they meet indicates the presence of a loop.

Once we have detected the loop, we can determine its length by counting the number of steps it takes for the pointers to meet again.

Algorithm:

  • Use two pointers, slow and fast.
  • Move slow by one step and fast by two steps.
  • If they meet, there is a loop.
  • Once the loop is detected, count the length by moving one of the pointers until it meets the other pointer again.

Code:

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

int lengthOfLoop(ListNode *head) {
    ListNode *slow = head, *fast = head;
    bool loopExists = false;

    // Detect loop
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            loopExists = true;
            break;
        }
    }

    // If loop exists, find its length
    if (loopExists) {
        int length = 1;
        slow = slow->next;
        while (slow != fast) {
            slow = slow->next;
            length++;
        }
        return length;
    } else {
        return 0; // No loop
    }
}

int main() {
    ListNode *head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    head->next->next->next->next->next = head->next; // Create loop

    cout << "Length of loop: " << lengthOfLoop(head) << endl;

    // Free memory
    ListNode *temp;
    while (head != nullptr) {
        temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}
OR:
#include <bits/stdc++.h>
using namespace std;

// Definition of singly linked list:
struct ListNode
{
    int val;
    ListNode *next;
    ListNode()
    {
        val = 0;
        next = NULL;
    }
    ListNode(int data1)
    {
        val = data1;
        next = NULL;
    }
    ListNode(int data1, ListNode *next1)
    {
        val = data1;
        next = next1;
    }
};

class Solution {
public:
    // Function to find the length of the loop 
    int findLength(ListNode* slow, ListNode* fast) {
        // Count to keep track of nodes encountered in loop
        int cnt = 1;
        
        // Move fast by one step
        fast = fast->next;
        
        // Traverse fast till it reaches back to slow
        while (slow != fast) {
            /* At each node 
            increase count by 1
            move fast forward 
            by one step */
            cnt++;
            fast = fast->next;
        }
        
        /* Loop terminates 
        when fast reaches slow again 
        and the count is returned*/
        return cnt;
    }

    // Function to find the length of the loop 
    int findLengthOfLoop(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        // Traverse the list to detect a loop
        while (fast != nullptr && fast->next != nullptr) {
            // Move slow one step
            slow = slow->next;
            // Move fast two steps
            fast = fast->next->next;

            // If the slow and fast pointers meet
            // there is a loop
            if (slow == fast) {
                // return the number of nodes 
                return findLength(slow, fast);
            }
        }

        /*If the fast pointer 
        reaches the end, 
        there is no loop*/
        return 0;
    }
};

int main() {
    // Create a sample linked list with a loop
    ListNode* head = new ListNode(1);
    ListNode* second = new ListNode(2);
    ListNode* third = new ListNode(3);
    ListNode* fourth = new ListNode(4);
    ListNode* fifth = new ListNode(5);

    // Create a loop from fifth to second
    head->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = fifth;
    fifth->next = second;

    Solution solution;
    int loopLength = solution.findLengthOfLoop(head);
    if (loopLength > 0) {
        cout << "Length of the loop: " << loopLength << endl;
    } else {
        cout << "No loop found in the linked list." << endl;
    }

    return 0;
}

Complexity Analysis:

  • Time Complexity: O(n)
    • Because the code traverses the entire linked list once, where n is the number of nodes in the list.
  • Space Complexity: O(1)
    • Because the code uses only a constant amount of additional space, regardless of the linked list's length. This is achieved by using two pointers (slow and fast) to detect the loop without any significant extra memory usage, resulting in constant space complexity O(1).
Your experience on this site will be improved by allowing cookies Cookie Policy