L17: Find the Starting Point of a Loop/Cycle in a Linked List

Finding the starting node of a cycle within a Linked List is a classic pointer-manipulation and cycle-detection problem in data structures and algorithms. Given a Linked List that may or may not contain a loop, the objective is to return the entire node where the cycle begins, or return null if the list is linear and cycle-free.

1. Problem Statement & Operational Rules

Before attempting to find the starting node, you must understand the fundamental contract of the problem:

• Cycle Presence: The Linked List may either be completely linear (straight path ending in null) or contain a tail pointing back to an earlier node, forming a loop.
• Return Requirements:
  • If a loop exists, return the exact memory node (e.g., ListNode* in C++ or Node in Java) where the loop begins, not the integer value stored inside the node.
  • If no loop exists, return null.
• Prerequisite: Mastery of the Tortoise and Hare algorithm (Floyd's Cycle-Finding Algorithm) and hashing fundamentals for cycle detection is strongly recommended before tackling the starting point.

2. Real-Life Analogy: The Circular Racing Track

To visualize a loop in a Linked List, think of a circular running track with a long entry path:

• Imagine a running track where runners enter from a straight corridor (the linear part of the Linked List) and eventually merge onto a circular loop.
• If you want to find the exact gate where runners first enter the circular loop from the straight corridor, simply tracking how many times you saw a runner's jersey number won't work if multiple runners wear the same number.
• You must identify the unique starting gate itself by tracking individual runners or using relative speeds to measure exact track geometries.

3. Naive Approach: The Hashing Technique

The most intuitive brute-force approach to finding a repeated node is utilizing extra memory to keep track of every node you visit during traversal.

How Hashing Works

1. Instantiate a Hash Map (or Hash Set) to store references to visited nodes: unordered_map<Node*, int> in C++ or HashMap<Node, Integer> in Java.
2. Traverse the Linked List sequentially using a temporary pointer (temp).
3. For every node encountered, check if it already exists in your map.
4. If it does not exist, insert the node into the map and advance temp.
5. If it already exists, that node is your loop's starting point. Return temp.
6. If temp hits null, the list is linear; return null.

Why Store the Entire Node Instead of Values?

Storing node values (e.g., storing integer 15) fails if duplicate values exist earlier in the linear path. By storing the entire node reference as the map key, you guarantee unique memory identification.

Hashing Code Structure

Node* detectStartingPointHashing(Node* head) {
    unordered_map<Node*, int> visitedNodes;
    Node* temp = head;
    
    while (temp != nullptr) {
        // Check if node is already in the map
        if (visitedNodes.find(temp) != visitedNodes.end()) {
            return temp; // First duplicated node is the starting point
        }
        visitedNodes[temp] = 1;
        temp = temp->next;
    }
    return nullptr; // Reached end, no loop
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$ for traversing up to $N$ nodes, with map insertion/lookup operations taking $\mathcal{O}(1)$ on average (or $\mathcal{O}(\log N)$ for ordered maps).
• Space Complexity: $\mathcal{O}(N)$ because every node in the linked list is stored inside the hash map.

4. The Interviewer's Objection: Space Optimization

While the hashing approach works, interviewers will typically reject the $\mathcal{O}(N)$ extra space complexity and demand an $\mathcal{O}(1)$ auxiliary space solution.

To eliminate extra memory structures, we must leverage the structural properties of pointer movement using Floyd's Tortoise and Hare Algorithm.

5. Step-by-Step Optimal Approach: Tortoise & Hare Algorithm

The optimal solution is divided into two distinct phases:

Phase 1: Detecting the Loop

• Initialize two pointers (slow and fast) pointing to head.
• Move slow by 1 step (slow = slow->next) and fast by 2 steps (fast = fast->next->next).
• If slow and fast meet at the same node, a loop exists.
• If fast or fast->next hits null, the list is linear; terminate and return null.

Phase 2: Finding the Starting Point

• Once a collision occurs, keep one pointer (e.g., fast) at the exact collision node.
• Relocate the other pointer (slow) back to the head of the Linked List.
• Now, advance both pointers (slow and fast) by exactly 1 step at a time.
• The exact node where they collide for the second time is guaranteed to be the starting point of the loop.

6. Complete Implementation (C++ & Java)

C++ Implementation

class Solution {
public:
    Node* detectCycle(Node* head) {
        if (head == nullptr || head->next == nullptr) return nullptr;
        
        Node* slow = head;
        Node* fast = head;
        bool hasLoop = false;
        
        // Phase 1: Detect Loop using Tortoise and Hare
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            
            if (slow == fast) {
                hasLoop = true;
                break;
            }
        }
        
        // If no loop is detected, return null
        if (!hasLoop) return nullptr;
        
        // Phase 2: Find the Starting Point
        slow = head; // Reset slow to head
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next; // Move both by 1 step
        }
        
        return slow; // Starting node of the loop
    }
};

Java Implementation

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == nullptr || head.next == null) return null;
        
        ListNode slow = head;
        ListNode fast = head;
        boolean hasLoop = false;
        
        // Phase 1: Detect Loop
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                hasLoop = true;
                break;
            }
        }
        
        if (!hasLoop) return null;
        
        // Phase 2: Find Starting Point
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        
        return slow;
    }
}

7. Mathematical Proof & Intuition: Why Does Phase 2 Work?

Understanding why resetting one pointer to the head and moving both at equal speeds pinpoints the loop start is essential for technical interviews.

Distance Breakdown

Let:

• $L_1$ = Distance from the head to the starting point of the loop.
• $L_2$ = Distance from the starting point of the loop to the initial collision point.
• $C$ = Total length of the loop cycle.

When slow and fast collide during Phase 1:

• The slow pointer has traveled a distance of: $L_1 + L_2$
• The fast pointer (moving at twice the speed) has traveled twice the distance of slow: $2(L_1 + L_2)$

Equation Derivation

The total distance traveled by fast can also be expressed as the distance to the loop start plus complete loops around the cycle ($n \times C$) plus the distance $L_2$:

Equating the two expressions for fast's distance:

Simplify the equation by subtracting $(L_1 + L_2)$ from both sides:

The Core Conclusion

The equation $L_1 = n \cdot C - L_2$ proves that:

• If you start a pointer at the head and travel $L_1$ steps, you arrive at the starting node.
• If you start a pointer at the collision point and travel $n$ full loops minus $L_2$ steps, you land on the exact same starting node.

Moving both slow (from head) and fast (from the collision point) at 1 step per interval guarantees they will meet precisely at the loop's starting node.

8. Summary and Key Takeaways

• Problem Goal: Locate and return the exact node where a Linked List cycle begins, or return null if the list is linear.
• Flawed Brute Force: Hashing nodes in a Map/Set works and yields $\mathcal{O}(N)$ time, but consumes $\mathcal{O}(N)$ extra space.
• Optimal Space Strategy: Floyd’s Tortoise and Hare algorithm achieves the optimal $\mathcal{O}(1)$ auxiliary space.
• Phase 1 (Detection): Initialize slow (1x speed) and fast (2x speed) from head until they collide. If fast hits null, no cycle exists.
• Phase 2 (Localization): Relocate slow back to head, keep fast at the collision point, and advance both at 1 step per tick until they meet again at the loop entry node.
• Mathematical Guarantee: The geometric offset $L_1 = n \cdot C - L_2$ mathematically proves that stepping from head and the collision point at equal rates forces convergence at the loop start.