91. Detect a 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 'Yes' if the list has a loop, otherwise 'No'.

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 'Yes' if the list contains a loop, otherwise print 'No'.

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

This exact slow/fast meeting technique is the FIRST step of several harder problems in this category (finding the loop's length, finding its starting node) - mastering just the detection step here makes those natural extensions.

Check whether a linked list has a cycle - some node's next pointer looping back to an earlier node instead of eventually reaching null. Brute force: Keep a hash set of every node visited, and check before visiting each new node whether it's already in the set - if so, there's a loop. This works but costs O(n) extra space, unlike the pointer-based approach which needs none. Optimised: Floyd's cycle detection (slow/fast pointers) proves that if a loop exists, the fast pointer MUST eventually meet the slow pointer - since the fast pointer gains exactly one step of relative distance on the slow pointer per iteration while both are circling within the loop, it can never simply 'skip past' the slow pointer forever, guaranteeing a meeting within a bounded number of steps.

Traverse the list from the head, keeping a hash set of every node visited so far, and before moving to the next node check whether it is already in the set. If a node is ever found already present in the set, the list loops back on itself, so report "Yes"; if the traversal instead reaches a null next pointer, there is no loop, so report "No". Time: O(n) Space: O(n)

Traverse the list, and for every node visited, flip a boolean "visited" flag stored directly on that node itself instead of recording it in an external set; before moving on, check whether the next node's flag is already set, which would indicate a loop. This eliminates the extra hash set entirely, trading it for a small amount of state living on each node, though it does permanently modify the list's nodes, which isn't always acceptable. Time: O(n) Space: O(1)

Use Floyd's "tortoise and hare" technique: start two pointers at the head, advancing the slow pointer one node and the fast pointer two nodes on every iteration. If there is a loop, the fast pointer will eventually lap the slow one and both will point to the same node; if there is no loop, the fast pointer (or its next pointer) reaches null first. This detects the loop with no extra memory and without modifying any of the list's nodes. Time: O(n) Space: O(1)

1. Use two pointers: a SLOW pointer moving one step at a time, and a FAST pointer moving two steps at a time. 2. If the list has NO loop, the fast pointer will eventually reach the end (null). 3. If the list DOES have a loop, the fast pointer will eventually catch up to and MEET the slow pointer somewhere inside the loop - guaranteed, since the fast pointer gains one extra step of distance on the slow pointer every iteration while both are within the loop.

Time: O(n) - the two pointers meet (or the fast pointer reaches null) within a number of steps proportional to the list's size. Space: O(1) - just two pointers, no extra data structure needed.

pos = -1 (no loop), pos = 0 (the entire list loops back to the head), and n = 10^5 for Floyd's algorithm performance.

Be ready to explain WHY the fast pointer can't simply 'jump over' the slow pointer without ever meeting it - the relative-distance argument (closing by exactly one step per iteration once inside the loop) is the crux of Floyd's algorithm's correctness proof.