244. Find the Starting Point 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 0-indexed position where the loop begins, or -1 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 if there is no loop). Output: Print a single integer - the 0-indexed position where the loop begins, or -1 if there is no loop.

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

This is widely regarded as one of the most elegant, non-obvious tricks in all of classic algorithm interviewing - the reset-to-head technique reveals a genuinely beautiful mathematical relationship, well worth deeply understanding rather than just memorizing.

Given a linked list with a loop, find the exact node where that loop begins. Brute force: Keep a hash set of visited nodes, and the moment a node is revisited, that's the loop's start - this works but costs O(n) extra memory, when the elegant two-phase pointer technique needs none. Optimised: The mathematical property behind Floyd's algorithm guarantees that, after the slow and fast pointers first meet, moving one pointer back to the head and advancing BOTH one step at a time causes them to meet again PRECISELY at the loop's starting node - a beautiful, provable consequence of the distances involved (grounded in the relationship between the distance to the loop start and the loop's own length), needing zero extra memory.

Traverse the list from the head, and for every node visited, compare it (by identity/index) against every previously visited node in a growing list to check whether it has already been seen. The first node found to repeat marks the start of the loop, since that is the first node reachable twice; if traversal runs off the end (reaches a null next) without any repeat, there is no loop. This is correct but pays a quadratic cost because each new node is checked against all prior nodes individually. Time: O(n^2) Space: O(n)

Traverse the list from the head while inserting each visited node into a hash set. Before inserting, check whether the node is already present in the set; the first node that is already present is exactly the start of the loop, since it is the first node the traversal revisits. If the traversal reaches the end of the list (a null next pointer) before any repeat is found, there is no loop and the answer is -1. This is a direct, correct approach with a single linear pass, at the cost of extra memory for the set. Time: O(n) Space: O(n)

Move a slow pointer one step and a fast pointer two steps at a time from the head; if there is a loop, the two pointers are guaranteed to meet somewhere inside it. Once they meet, reset one pointer to the head and advance both remaining pointers one step at a time; the node where they next meet is exactly the starting node of the loop, by the standard mathematical property of Floyd's algorithm relating the pre-loop length and loop length. If the fast pointer ever reaches a null next pointer, there is no loop and the answer is -1. This finds the loop start in a single pass of pointer movement with no extra memory. Time: O(n) Space: O(1)

1. Use Floyd's algorithm to find the meeting point of a slow and fast pointer inside the loop. 2. Once they meet, RESET one pointer back to the head of the list, keeping the other at the meeting point. 3. Advance BOTH pointers one step at a time (not two anymore) - they are guaranteed to meet again exactly at the loop's starting node.

Time: O(n) - both phases (finding the meeting point, then finding the loop start) are linear in the list's size. Space: O(1) - just pointers, no extra data structure.

pos = -1 (no loop at all); pos = 0 (the entire list loops back to its head); pos = n-1 (the last node loops to itself); n = 10^5 for performance.

Be ready to at least sketch the mathematical proof for why resetting one pointer to the head works - interviewers highly value seeing that you understand WHY this elegant trick works, not just that you've memorized the steps.