Find Length of Loop

Summary

Find the length of a loop in a linked list. The problem involves identifying a cycle in the linked list and then finding its length.

Detailed Explanation

Given a linked list, find the length of the loop. A loop is formed when there are duplicate nodes (not necessarily adjacent) in the linked list. This can be solved by using Floyd's Cycle-Finding Algorithm (also known as the "tortoise and hare" algorithm).

Here's how it works:

Initialize two pointers, slow and fast, to the head of the linked list.
Move both pointers one step at a time. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time.
If there is a loop in the linked list, the fast pointer will eventually meet the slow pointer within the loop.
Once they meet, move both pointers to the head of the linked list and repeat steps 2-3 until they meet again. The distance between their meeting points is the length of the loop.

Here's an ASCII art diagram:

   A -> B -> C -> D -> E -> F
      |         |
      +---------+

In this example, nodes E and F form a cycle.

Time complexity: O(n), where n is the number of nodes in the linked list. Space complexity: O(1).

Optimized Solutions

Java

public int findLengthOfLoop(Node head) { 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; // no loop found } int length = 1; slow = slow.next; fast = fast.next.next; while (slow != fast) { slow = slow.next; fast = fast.next.next; length++; } return length; }