LL 8 - Length of the Loop

Problem statement

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.

Example:

Input: Linked List: 4 -> 10 -> 3 -> 5 -> 10(at position 2)
Output: Length of cycle = 3

Explanation: The cycle is 10, 3, 5.

Solution

Brute Force Approach

1. Initialize a hash map (dictionary) to store each node and its corresponding timer/count.

   • As you traverse the linked list, keep track of the current timer or count.

   • For each node encountered, store its reference in the hash map along with the timer or count.

2. While traversing the linked list:

   • If the current node is not in the hash map, add it along with the current timer or count.

   • If the current node is already in the hash map, calculate the difference between the current timer or count and the stored timer or count for that node. This difference represents the length of the cycle (if there is one).

3. Return the cycle length (if any) or a default value 0 if no cycle is found.

public class Solution
{
    public static int lengthOfLoop(Node head) {
        // Write your code here
        Map<Node, Integer> map = new HashMap<>();

        Node temp = head;
        int timer = 1;
        while(temp!=null){
            if(map.containsKey(temp)) return timer - map.get(temp);
            map.put(temp, timer);
            temp = temp.next;
            timer += 1;
        }
        return 0;
    }
}

Optimal Approach

1. Initialization:

   • We start with two pointers: a slow pointer (tortoise) and a fast pointer (hare).

   • Both pointers begin at the head of the linked list.

2. Moving Through the List:

   • The slow pointer advances one step at a time (moves to the next node).

   • The fast pointer advances two steps at a time (skips a node).

3. Detecting a Cycle:

   • If there is no cycle, the fast pointer will eventually reach the end of the list (i.e., it will become null), and we can conclude that there’s no cycle.

   • If there is a cycle, the fast pointer will eventually catch up to the slow pointer within the loop. This collision point is where the two meet.

4. Calculating the Length of the Cycle:

   • Once the collision occurs, we stop the slow pointer (tortoise) and keep the fast pointer (hare) where it is.

   • Now we move both pointers one step at a time until they meet again. The number of steps taken by the fast pointer during this process gives us the length of the cycle.

public class Solution
{
    public static int cycleLength(Node slow, Node fast){
        int length = 1;
        fast = fast.next;

        while(slow!=fast){
            fast = fast.next;
            length+=1;
        }
        return length;
    }
    public static int lengthOfLoop(Node head) {
        if(head == null) return 0;

        Node slow = head;
        Node fast = head;

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

            if(slow==fast) return cycleLength(slow, fast);
        }
        return 0;
    }
}