Problem: Linked List Cycle (Easy)

1. Problem Statement

Mental Model

Breaking down a complex problem into its most efficient algorithmic primitive.

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer.

Return true if there is a cycle in the linked list. Otherwise, return false.

Input: head = [3,2,0,-4], pos = 1 (Node -4 points back to Node 2)
Output: true

2. The Mental Model: The "Track and Field" Intuition

Imagine two runners on a circular track.

Runner A (Slow): Moves 1 step at a time.
Runner B (Fast): Moves 2 steps at a time.

If the track is linear (no cycle), the Fast runner will reach the end and the race is over. However, if there is a Cycle, the Fast runner will eventually enter the loop and, because they are moving faster, they will eventually "Lap" the Slow runner. They will meet at some point inside the loop.

This is known as Floyd’s Cycle-Finding Algorithm.

3. Visual Execution (The Meeting Point)

graph LR
    subgraph "Detecting the Loop"
        H((3)) --> N1((2)) --> N2((0)) --> N3((-4))
        N3 -.-> N1
    end
    
    subgraph "Pointer Positions"
        P1[Step 1: S=3, F=3]
        P2[Step 2: S=2, F=0]
        P3[Step 3: S=0, F=2]
        P4[Step 4: S=-4, F=-4 | Match!]
    end

4. Java Implementation (Optimal)

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) return false;
    
    ListNode slow = head;
    ListNode fast = head;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;        // Move 1 step
        fast = fast.next.next;   // Move 2 steps
        
        // If they meet, there is a cycle
        if (slow == fast) {
            return true;
        }
    }
    
    // Fast reached the end of the list
    return false;
}

5. Verbal Interview Script (Staff Tier)

Interviewer: "Why is the space complexity O(1)?"

You: "The space complexity is constant because we only maintain two pointer references (slow and fast) regardless of the size of the input list. Unlike a HashSet approach, which would require $O(N)$ space to store every node we've visited, Floyd's algorithm allows us to detect the cycle purely through the mathematical relationship between the speeds of the two pointers. This is the gold standard for cycle detection in memory-constrained environments."

6. Staff-Level Follow-Ups

Follow-up 1: "Where does the cycle start?"

The Answer: "This is the 'Linked List Cycle II' problem. Once the pointers meet, I would reset the slow pointer to the head and keep fast at the meeting point. Then, I'd move both pointers 1 step at a time. The point where they meet again is the exact start of the cycle. The mathematical proof relies on the distance from the head to the cycle start being equal to the distance from the meeting point back to the start (modulo cycle length)."

Follow-up 2: "What happens if fast moves 3 steps instead of 2?"

The Answer: "The algorithm would still work, but it might actually take longer or be less efficient. Moving by 2 steps is the smallest difference that guarantees a meeting in a single loop. If the speed difference is too large, the fast pointer might 'jump over' the slow pointer multiple times before they land on the same node."

7. Performance Nuances (The Java Perspective)

Null Safety: In the while condition, the order of checks is vital. fast != null && fast.next != null ensures we never call .next on a null reference.
Primitive References: In Java, pointers are just memory addresses. Comparing slow == fast is an $O(1)$ reference equality check, which is extremely fast and doesn't involve any equals() or hashing logic.

6. Staff-Level Verbal Masterclass (Communication)

Interviewer: "How would you defend this specific implementation in a production review?"

You: "In a mission-critical environment, I prioritize the Big-O efficiency of the primary data path, but I also focus on the Predictability of the system. In this implementation, I chose a iterative two-pointer approach. While a recursive solution is more readable, I would strictly monitor the stack depth. If this were to handle skewed inputs, I would immediately transition to an explicit stack on the heap to avoid a StackOverflowError. From a memory perspective, I leverage localized objects to ensure that we minimize the garbage collection pauses (Stop-the-world) that typically plague high-throughput Java applications."

7. Global Scale & Distributed Pivot

When a problem like this is moved from a single machine to a global distributed architecture, the constraints change fundamentally.

Data Partitioning: We would shard the input space using Consistent Hashing. This ensures that even if our dataset grows to petabytes, any single query only hits a small subset of our cluster, maintaining logarithmic lookup times.
State Consistency: For problems involving state updates (like DP or Caching), we would use a Distributed Consensus protocol like Raft or Paxos to ensure that all replicas agree on the final state, even in the event of a network partition (The P in CAP theorem).

8. Performance Nuances (The Staff Perspective)

Cache Locality: Accessing a 2D matrix in row-major order (reading [i][j] then [i][j+1]) is significantly faster than column-major order in modern CPUs due to L1/L2 cache pre-fetching. I always structure my loops to align with how the memory is physically laid out.
Autoboxing and Generics: In Java, using List<Integer> instead of int[] can be 3x slower due to the overhead of object headers and constant wrapping. For the most performance-sensitive sections of this algorithm, I advocate for primitive specialized structures.

Key Takeaways

****Runner A (Slow): Moves 1 step at a time.
****Runner B (Fast): Moves 2 steps at a time.
The Answer: "This is the 'Linked List Cycle II' problem. Once the pointers meet, I would reset the slow pointer to the head and keep fast at the meeting point. Then, I'd move both pointers 1 step at a time. The point where they meet again is the exact start of the cycle. The mathematical proof relies on the distance from the head to the cycle start being equal to the distance from the meeting point back to the start (modulo cycle length)."