92. Find the Length of the Loop in a Linked List

A singly linked list has n node values. Its last node's next pointer is connected back to the node at 0-indexed position pos (or there is no loop if pos is -1). Print the number of nodes in the loop, or 0 if there is no loop.

Input: The first line contains an integer n. The second line contains n space-separated integers, the list's values. The third line contains pos, the 0-indexed position the last node's next pointer connects back to, or -1 for no loop. Output: Print a single integer - the number of nodes in the loop, or 0 if there is no loop.

1 <= n <= 10^5, -1 <= pos < n

This directly builds on 'Detect a Loop in a Linked List' - the loop-length measurement is simply an additional step performed AFTER the same slow/fast pointer detection technique already confirms a loop exists.

Given a linked list that may contain a loop, find how many nodes make up that loop. Brute force: Keep a hash set of visited nodes with their visit order/index, and once a node is revisited, compute the difference between the current step count and its first-visit step count - this works but costs O(n) extra space, when the pointer-based approach needs none. Optimised: Once Floyd's algorithm confirms a loop by finding a meeting point INSIDE the loop, that meeting point is a valid 'anchor' to measure the loop's length from - walking forward from it and counting steps until returning to the same node directly gives the length, with no need to track visited nodes explicitly.

Use a slow pointer that moves one step at a time and a fast pointer that moves two steps at a time. If there's a loop, the fast pointer will eventually catch up to and meet the slow pointer somewhere inside the loop; if the fast pointer reaches the end (null), there is no loop. Once they meet, count the loop's length by walking a single pointer forward from the meeting point, incrementing a counter, until it returns to that same node. This eliminates the need for any hash set, using only a constant number of pointers instead of memory proportional to the list. Time: O(n) Space: O(1)

Traverse the list one node at a time, storing each visited node reference in a hash set along with the step number at which it was visited. If a node is encountered that is already in the set, a loop exists, and its length is simply the current step number minus the stored step number of that node; if you reach the end (a null next pointer) with no repeat, there is no loop. This is correct and simple, but it requires extra memory proportional to how far into the list you travel before finding the repeat. Time: O(n) Space: O(n)

This is the same Floyd's tortoise-and-hare technique, but the meeting-and-measuring is done in the tightest possible way: as soon as slow and fast meet, keep only the fast pointer moving one step at a time from that point, counting steps, until it comes back around to the meeting node - there is no need for a second detection phase or for locating the start of the loop, since only the loop's length is required. This achieves the theoretical best possible complexity for this problem, O(n) time (every node in the loop must be visited to count it) and O(1) space, in the fewest possible passes over the list. Time: O(n) Space: O(1)

1. First detect the loop using Floyd's algorithm (slow/fast pointers) - if they meet, a loop exists at that meeting point. 2. From the meeting point, keep ONE pointer moving forward one step at a time, counting steps, until it returns to that SAME meeting point. 3. That count is exactly the loop's length; if no loop was detected, the length is 0.

Time: O(n) - detecting the loop and then measuring its length are both linear in the list's size. Space: O(1) - just pointers and a step counter, no extra data structure.

pos = -1 (loop length 0), pos = 0 (the loop includes every node), and n = 10^5 for performance.

Be ready to explain why the meeting point (found by Floyd's algorithm) is guaranteed to be SOMEWHERE INSIDE the loop, making it a valid starting point for measuring the loop's own length by simply walking around once.