Find length of Loop

JavaView on GFG

Time: O(n)

Space: O(1)

Problem Overview

Find length of cycle in linked list.

See our study guide for structured GFG and LeetCode practice.

Intuition

Find length of cycle in linked list. Floyd detection then count cycle length.

Algorithm

1Floyd slow/fast: detect cycle. From meeting point, advance one pointer until it returns. Count steps.

Common Pitfalls

• After cycle detected: keep one pointer at meeting point, advance other until it loops back. O(n).

Find length of Loop.java

Java

// Approach: Floyd's cycle detection to find meeting point, then count loop length by traversing the cycle.
// Time: O(n) Space: O(1)
class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}

class Solution {
    // Function to find the length of a loop in the linked list.
    public int countNodesinLoop(Node head) {
        boolean loop = false;

        Node slow = head;
        Node fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                loop = true;
                break;
            }
        }

        if (!loop)
            return 0;

        int count = 1;
        fast = fast.next;

        while (fast != slow) {
            count++;
            fast = fast.next;
        }

        return count;
    }
}

class Solution1 {
    // Function to find the length of a loop in the linked list.
    public int countNodesinLoop(Node head) {
        Node slow = head;
        Node fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                int count = 1;
                Node temp = slow.next;
                while (temp != slow) {
                    count++;
                    temp = temp.next;
                }
                return count;
            }
        }

        return 0;
    }
}

Was this solution helpful?