Linked List Cycle II - Start of Cycle

🎯

Linked List Cycle II - Start of Cycle

mediumTWO_POINTERAmazonMicrosoftGoogle

Imagine a train track that loops back on itself. You want to find exactly where the loop starts so you can fix it.

💡 This problem asks you to find the start of a cycle in a linked list. Beginners often struggle because detecting a cycle is one step, but finding the exact node where the cycle begins requires deeper insight and a clever approach. Think of it like finding the entrance to a circular tunnel rather than just knowing the tunnel exists.

📋

Problem Statement

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null. A cycle exists if a node's next pointer points to a previously visited node in the list.

The number of nodes in the list is in the range [0, 10^5].Node values are arbitrary and not necessarily unique.You must not modify the linked list.Expected time complexity is O(n) and space complexity is O(1).

💡

Example

Input"head = [3,2,0,-4], pos = 1"

OutputReference to node with value 2

The tail connects to the second node (index 1), so the cycle starts at node with value 2.

Input"head = [1,2], pos = 0"

OutputReference to node with value 1

The tail connects to the first node, so the cycle starts at node with value 1.

Input"head = [1], pos = -1"

Outputnull

No cycle exists in the list.

• Empty list (head = null) → output: null
• Single node with no cycle → output: null
• Single node with cycle to itself → output: node itself
• Cycle starts at head → output: head node

⚠️

Common Mistakes

Returning the meeting point of slow and fast as cycle start

Incorrect cycle start node returned, failing test cases

✅ After detecting cycle, reset one pointer to head and move both one step until they meet

Not checking for null before accessing fast.next

Runtime null pointer exception or segmentation fault

✅ Always check fast and fast.next are not null before moving fast pointer

Using extra space when the problem expects O(1) space

Interviewer rejects solution for not optimizing space

✅ Use Floyd’s cycle detection instead of hash sets

Infinite loop if cycle detection loop condition is incorrect

Code runs forever or times out

✅ Use proper while loop conditions and break when pointers meet

Not handling empty list or single node list correctly

Null pointer exceptions or wrong output

✅ Add checks for null head and single node cases

🧠

Brute Force (Hash Set to Detect Cycle Start)

💡 This approach uses extra memory to track visited nodes. It is straightforward and helps beginners understand the problem by explicitly checking for repeats. Think of it as leaving breadcrumbs to know if you've been somewhere before.

Intuition

Traverse the list and store each visited node in a hash set. When you encounter a node already in the set, that node is the start of the cycle.

Algorithm

1. Initialize an empty hash set to store visited nodes.
2. Traverse the linked list from the head node.
3. For each node, check if it is in the hash set.
4. If yes, return that node as the cycle start.
5. If no, add the node to the hash set and continue.
6. If traversal ends (null), return null indicating no cycle.

💡 This algorithm is easy to follow because it directly checks for repeated nodes, but it uses extra memory which is not optimal.

</>

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def detectCycle(head):
    visited = set()
    current = head
    while current:
        if current in visited:
            return current
        visited.add(current)
        current = current.next
    return None

# Example usage:
# node4 = ListNode(-4)
# node3 = ListNode(0, node4)
# node2 = ListNode(2, node3)
# node1 = ListNode(3, node2)
# node4.next = node2  # cycle
# print(detectCycle(node1).val)  # Output: 2

Line Notes

visited = set()Create a set to keep track of nodes we've seen to detect repeats.

while current:Traverse nodes until we reach the end or find a cycle.

if current in visited:If current node is already visited, we've found the cycle start.

visited.add(current)Mark current node as visited before moving on.

import java.util.HashSet;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
        HashSet<ListNode> visited = new HashSet<>();
        ListNode current = head;
        while (current != null) {
            if (visited.contains(current)) {
                return current;
            }
            visited.add(current);
            current = current.next;
        }
        return null;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     ListNode node4 = new ListNode(-4);
    //     ListNode node3 = new ListNode(0);
    //     ListNode node2 = new ListNode(2);
    //     ListNode node1 = new ListNode(3);
    //     node1.next = node2;
    //     node2.next = node3;
    //     node3.next = node4;
    //     node4.next = node2; // cycle
    //     Solution sol = new Solution();
    //     System.out.println(sol.detectCycle(node1).val); // Output: 2
    // }
}

Line Notes

HashSet<ListNode> visited = new HashSet<>()Use a hash set to track visited nodes for cycle detection.

while (current != null)Traverse the linked list until the end or cycle found.

if (visited.contains(current))If node already visited, cycle start found.

visited.add(current)Add current node to visited set before moving on.

#include <iostream>
#include <unordered_set>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode*> visited;
        ListNode* current = head;
        while (current != nullptr) {
            if (visited.find(current) != visited.end()) {
                return current;
            }
            visited.insert(current);
            current = current->next;
        }
        return nullptr;
    }
};

// Example usage:
// int main() {
//     ListNode* node4 = new ListNode(-4);
//     ListNode* node3 = new ListNode(0);
//     ListNode* node2 = new ListNode(2);
//     ListNode* node1 = new ListNode(3);
//     node1->next = node2;
//     node2->next = node3;
//     node3->next = node4;
//     node4->next = node2; // cycle
//     Solution sol;
//     cout << sol.detectCycle(node1)->val << endl; // Output: 2
//     return 0;
// }

Line Notes

unordered_set<ListNode*> visited;Use a hash set to store visited nodes for cycle detection.

while (current != nullptr)Traverse nodes until end or cycle found.

if (visited.find(current) != visited.end())If current node already visited, cycle start found.

visited.insert(current);Mark current node as visited before moving forward.

function ListNode(val) {
    this.val = val;
    this.next = null;
}

var detectCycle = function(head) {
    const visited = new Set();
    let current = head;
    while (current !== null) {
        if (visited.has(current)) {
            return current;
        }
        visited.add(current);
        current = current.next;
    }
    return null;
};

// Example usage:
// let node4 = new ListNode(-4);
// let node3 = new ListNode(0);
// let node2 = new ListNode(2);
// let node1 = new ListNode(3);
// node1.next = node2;
// node2.next = node3;
// node3.next = node4;
// node4.next = node2; // cycle
// console.log(detectCycle(node1).val); // Output: 2

Line Notes

const visited = new Set();Create a set to track visited nodes for cycle detection.

while (current !== null)Traverse the linked list until no more nodes or cycle found.

if (visited.has(current))If node already visited, cycle start found.

visited.add(current);Add current node to visited set before moving on.

⏱

Complexity

TimeO(n)

SpaceO(n)

We traverse each node once, but store each node in a hash set, so space grows linearly with n.

💡 For n=100,000 nodes, this means up to 100,000 insertions and lookups in the hash set, which is feasible but not optimal.

Interview Verdict: Accepted but not optimal

This approach works but uses extra memory, which is often not allowed in interviews. It's a good starting point to understand the problem.

🧠

Floyd’s Cycle Detection (Fast & Slow Pointers) to Detect Cycle

💡 This approach detects if a cycle exists without extra memory by using two pointers moving at different speeds. It is a classic technique that lays the foundation for finding the cycle start. However, note that this approach only detects the presence of a cycle and returns the meeting point inside the cycle, not the cycle start node.

Intuition

Use two pointers: slow moves one step at a time, fast moves two steps. If they meet, a cycle exists. If fast reaches null, no cycle.

Algorithm

1. Initialize two pointers, slow and fast, at the head.
2. Move slow by one step and fast by two steps in each iteration.
3. If fast or fast.next becomes null, return null (no cycle).
4. If slow equals fast, a cycle is detected; return the meeting node.

💡 This algorithm cleverly uses pointer speeds to detect cycles without extra memory, but it only detects presence, not the start.

</>

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def detectCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return slow  # cycle detected (meeting point)
    return None

# Example usage:
# node4 = ListNode(-4)
# node3 = ListNode(0, node4)
# node2 = ListNode(2, node3)
# node1 = ListNode(3, node2)
# node4.next = node2  # cycle
# print(detectCycle(node1).val)  # Output: 2 (meeting point, not cycle start)

Line Notes

slow = fast = headInitialize both pointers at the start of the list.

while fast and fast.next:Ensure fast pointer can move two steps safely.

slow = slow.nextMove slow pointer one step forward.

fast = fast.next.nextMove fast pointer two steps forward.

if slow == fast:If pointers meet, a cycle exists; return meeting point.

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return slow; // cycle detected (meeting point)
            }
        }
        return null;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     ListNode node4 = new ListNode(-4);
    //     ListNode node3 = new ListNode(0);
    //     ListNode node2 = new ListNode(2);
    //     ListNode node1 = new ListNode(3);
    //     node1.next = node2;
    //     node2.next = node3;
    //     node3.next = node4;
    //     node4.next = node2; // cycle
    //     Solution sol = new Solution();
    //     System.out.println(sol.detectCycle(node1).val); // Output: 2 (meeting point)
    // }
}

Line Notes

ListNode slow = head, fast = head;Initialize two pointers at the head.

while (fast != null && fast.next != null)Check that fast pointer can safely move two steps.

slow = slow.next;Move slow pointer one step.

fast = fast.next.next;Move fast pointer two steps.

if (slow == fast)Pointers meet means cycle detected; return meeting point.

#include <iostream>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                return slow; // cycle detected (meeting point)
            }
        }
        return nullptr;
    }
};

// Example usage:
// int main() {
//     ListNode* node4 = new ListNode(-4);
//     ListNode* node3 = new ListNode(0);
//     ListNode* node2 = new ListNode(2);
//     ListNode* node1 = new ListNode(3);
//     node1->next = node2;
//     node2->next = node3;
//     node3->next = node4;
//     node4->next = node2; // cycle
//     Solution sol;
//     std::cout << sol.detectCycle(node1)->val << std::endl; // Output: 2 (meeting point)
//     return 0;
// }

Line Notes

ListNode *slow = head, *fast = head;Initialize two pointers at the list head.

while (fast && fast->next)Ensure fast pointer can move two steps safely.

slow = slow->next;Move slow pointer one step.

fast = fast->next->next;Move fast pointer two steps.

if (slow == fast)Pointers meeting means cycle detected; return meeting point.

function ListNode(val) {
    this.val = val;
    this.next = null;
}

var detectCycle = function(head) {
    let slow = head, fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            return slow; // cycle detected (meeting point)
        }
    }
    return null;
};

// Example usage:
// let node4 = new ListNode(-4);
// let node3 = new ListNode(0);
// let node2 = new ListNode(2);
// let node1 = new ListNode(3);
// node1.next = node2;
// node2.next = node3;
// node3.next = node4;
// node4.next = node2; // cycle
// console.log(detectCycle(node1).val); // Output: 2 (meeting point)

Line Notes

let slow = head, fast = head;Initialize two pointers at the start.

while (fast !== null && fast.next !== null)Check fast pointer can move two steps.

slow = slow.next;Move slow pointer one step.

fast = fast.next.next;Move fast pointer two steps.

if (slow === fast)Pointers meeting means cycle detected; return meeting point.

⏱

Complexity

TimeO(n)

SpaceO(1)

Both pointers traverse the list at most a few times, so linear time. No extra memory used.

💡 For n=100,000 nodes, this means a few hundred thousand pointer moves, which is efficient and uses constant space.

Interview Verdict: Accepted and optimal for cycle detection

This is the standard approach to detect a cycle efficiently without extra memory, a must-know technique.

🧠

Floyd’s Algorithm to Find Cycle Start Node

💡 This approach extends Floyd’s cycle detection to find the exact node where the cycle begins, using a mathematical insight about pointer distances. It is the optimal solution expected in interviews.

Intuition

After detecting a cycle (slow == fast), reset one pointer to head and move both pointers one step at a time. The node where they meet again is the cycle start.

Algorithm

1. Use Floyd’s cycle detection to find the meeting point inside the cycle.
2. If no cycle, return null.
3. Initialize one pointer at head, another at meeting point.
4. Move both pointers one step at a time until they meet.
5. Return the meeting node as the cycle start.

💡 This algorithm uses the properties of cycle lengths and distances to find the start without extra memory.

</>

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def detectCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None
    ptr1 = head
    ptr2 = slow
    while ptr1 != ptr2:
        ptr1 = ptr1.next
        ptr2 = ptr2.next
    return ptr1

# Example usage:
# node4 = ListNode(-4)
# node3 = ListNode(0, node4)
# node2 = ListNode(2, node3)
# node1 = ListNode(3, node2)
# node4.next = node2  # cycle
# print(detectCycle(node1).val)  # Output: 2 (cycle start)

Line Notes

while fast and fast.next:Traverse list with two pointers to detect cycle.

if slow == fast:Pointers meet means cycle detected; break loop.

else: return NoneIf no cycle detected, return null.

ptr1 = headInitialize first pointer at head to find cycle start.

while ptr1 != ptr2:Move both pointers one step until they meet at cycle start.

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return null;
        }
        ListNode ptr1 = head;
        ListNode ptr2 = slow;
        while (ptr1 != ptr2) {
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }
        return ptr1;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     ListNode node4 = new ListNode(-4);
    //     ListNode node3 = new ListNode(0);
    //     ListNode node2 = new ListNode(2);
    //     ListNode node1 = new ListNode(3);
    //     node1.next = node2;
    //     node2.next = node3;
    //     node3.next = node4;
    //     node4.next = node2; // cycle
    //     Solution sol = new Solution();
    //     System.out.println(sol.detectCycle(node1).val); // Output: 2
    // }
}

Line Notes

while (fast != null && fast.next != null)Traverse list with two pointers to detect cycle.

if (slow == fast)Pointers meet means cycle detected; break loop.

if (fast == null || fast.next == null)No cycle if fast pointer reached end.

ListNode ptr1 = head;Initialize pointer at head to find cycle start.

while (ptr1 != ptr2)Move both pointers one step until they meet at cycle start.

#include <iostream>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                break;
            }
        }
        if (!fast || !fast->next) {
            return nullptr;
        }
        ListNode *ptr1 = head;
        ListNode *ptr2 = slow;
        while (ptr1 != ptr2) {
            ptr1 = ptr1->next;
            ptr2 = ptr2->next;
        }
        return ptr1;
    }
};

// Example usage:
// int main() {
//     ListNode* node4 = new ListNode(-4);
//     ListNode* node3 = new ListNode(0);
//     ListNode* node2 = new ListNode(2);
//     ListNode* node1 = new ListNode(3);
//     node1->next = node2;
//     node2->next = node3;
//     node3->next = node4;
//     node4->next = node2; // cycle
//     Solution sol;
//     std::cout << sol.detectCycle(node1)->val << std::endl; // Output: 2
//     return 0;
// }

Line Notes

while (fast && fast->next)Traverse list with two pointers to detect cycle.

if (slow == fast)Pointers meet means cycle detected; break loop.

if (!fast || !fast->next)No cycle if fast pointer reached end.

ListNode *ptr1 = head;Initialize pointer at head to find cycle start.

while (ptr1 != ptr2)Move both pointers one step until they meet at cycle start.

function ListNode(val) {
    this.val = val;
    this.next = null;
}

var detectCycle = function(head) {
    let slow = head, fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            break;
        }
    }
    if (fast === null || fast.next === null) {
        return null;
    }
    let ptr1 = head;
    let ptr2 = slow;
    while (ptr1 !== ptr2) {
        ptr1 = ptr1.next;
        ptr2 = ptr2.next;
    }
    return ptr1;
};

// Example usage:
// let node4 = new ListNode(-4);
// let node3 = new ListNode(0);
// let node2 = new ListNode(2);
// let node1 = new ListNode(3);
// node1.next = node2;
// node2.next = node3;
// node3.next = node4;
// node4.next = node2; // cycle
// console.log(detectCycle(node1).val); // Output: 2

Line Notes

while (fast !== null && fast.next !== null)Traverse list with two pointers to detect cycle.

if (slow === fast)Pointers meet means cycle detected; break loop.

if (fast === null || fast.next === null)No cycle if fast pointer reached end.

let ptr1 = head;Initialize pointer at head to find cycle start.

while (ptr1 !== ptr2)Move both pointers one step until they meet at cycle start.

⏱

Complexity

TimeO(n)

SpaceO(1)

Two pointer traversals each take linear time, no extra space used.

💡 For n=100,000 nodes, this approach efficiently finds the cycle start with minimal memory.

Interview Verdict: Accepted and optimal

This is the best-known solution for this problem and is expected in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, code the Floyd’s algorithm to find the cycle start (Approach 3) as it is optimal and expected.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Hash Set)	O(n)	O(n)	No	Yes	Mention only - never code due to extra space
2. Floyd’s Cycle Detection (Detect Cycle)	O(n)	O(1)	No	No (only detects cycle)	Mention as cycle detection step
3. Floyd’s Algorithm to Find Cycle Start	O(n)	O(1)	No	Yes (cycle start node)	Code this approach in 95% of interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to build intuition, then learn Floyd’s cycle detection, and finally master finding the cycle start.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Present the brute force approach using a hash set to detect cycle start.Step 3: Explain Floyd’s cycle detection to detect if a cycle exists without extra space.Step 4: Extend Floyd’s algorithm to find the exact cycle start node.Step 5: Code the optimal solution and test with edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your understanding of cycle detection, pointer manipulation, and ability to optimize space from naive to optimal solutions.

Common Follow-ups

• What if you cannot modify the list or use extra space? → Use Floyd’s algorithm.
• How to prove Floyd’s algorithm finds the cycle start? → Explain distance math between pointers.
• Can you detect cycle in a singly linked list without extra space? → Yes, Floyd’s algorithm.
• What if the list is extremely large? → Floyd’s algorithm still works efficiently.

💡 These follow-ups test your depth of understanding and ability to explain the algorithm’s correctness and limitations.

🔍

Pattern Recognition

When to Use

1) Problem involves linked list, 2) Need to detect cycle or loop, 3) Asked to find cycle start node, 4) Constraints require O(1) space

Signature Phrases

'return the node where the cycle begins''detect if a linked list has a cycle'

NOT This Pattern When

Problems involving two pointers but no cycle detection, e.g., two sum with sorted array, are different patterns.

Similar Problems

Linked List Cycle I - Detect if cycle exists using fast and slow pointersHappy Number - Detect cycle in number sequence using fast and slow pointers

Practice

1. You are given a singly linked list and an integer n. The task is to remove the n-th node from the end of the list in a single pass without using extra space for storing nodes. Which approach guarantees this optimal solution?

easy

A. Traverse the list twice: first to count nodes, second to remove the target node.

B. Sort the list first, then remove the node at position length - n.

C. Use two pointers with a fixed gap of n+1 nodes, moving together until the fast pointer reaches the end.

D. Use a dynamic programming approach to store intermediate results for each node.

Solution

1. Step 1: Understand the problem constraints

   The problem requires removing the n-th node from the end in one pass without extra storage.

2. Step 2: Identify the two-pointer technique for single-pass removal

   Using two pointers with a gap of n+1 nodes ensures the slow pointer stops just before the target node, allowing removal in one pass.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two-pointer approach is classic for single-pass linked list problems [OK]

Hint: Two pointers with gap n+1 enable single-pass removal [OK]

Common Mistakes:

• Using two passes instead of one
• Trying to sort the list which is unnecessary
• Confusing DP with linked list traversal

2. Examine the following buggy code for cycle detection using fast and slow pointers. Which line contains the subtle bug that can cause incorrect cycle detection or runtime error?

medium

A. Line 3: while fast and fast.next:

B. Line 5: slow = slow.next

C. Line 6: fast = fast.next.next

D. Line 4: if slow == fast:

Solution

1. Step 1: Understand pointer initialization and loop

   Both slow and fast start at head. The loop checks fast and fast.next to avoid null dereference.

2. Step 2: Identify when pointers are compared

   Comparing slow == fast before moving pointers causes immediate true at start (both at head), falsely detecting a cycle. Moving pointers first then comparing avoids this.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Comparison must happen after moving pointers to avoid false positive [OK]

Hint: Check pointers after moving, not before, to avoid false positives [OK]

Common Mistakes:

• Comparing pointers before moving them
• Not checking fast.next before advancing fast

3. What is the time and space complexity of the optimal single-pass two-pointer approach to find the middle node of a singly linked list with n nodes?

medium

A. Time: O(n), Space: O(1)

B. Time: O(n^2), Space: O(1)

C. Time: O(n), Space: O(n)

D. Time: O(log n), Space: O(1)

Solution

1. Step 1: Identify time complexity

   Fast pointer moves two steps per iteration, slow moves one; total iterations proportional to n -> O(n) time.

2. Step 2: Identify space complexity

   Only two pointers used, no extra data structures -> O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and constant space for two-pointer traversal [OK]

Hint: Two pointers traverse list once, no extra storage [OK]

Common Mistakes:

• Confusing space with O(n) due to recursion
• Assuming nested loops cause O(n^2)
• Thinking fast pointer halves complexity to O(log n)

4. Consider the following buggy code for finding the middle node of a linked list. Which line contains the subtle bug that can cause a runtime error?

medium

A. Line 4: while fast.next and fast.next.next:

B. Line 3: fast = head

C. Line 2: slow = head

D. Line 6: return slow

Solution

1. Step 1: Analyze loop condition

   The condition checks fast.next and fast.next.next but does not check if fast itself is null, which can cause AttributeError if fast is null.

2. Step 2: Identify fix

   Change condition to while fast and fast.next to safely access fast.next.next.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing fast null check causes runtime error on short lists [OK]

Hint: Always check fast pointer is not null before accessing next [OK]

Common Mistakes:

• Assuming fast.next is safe without checking fast
• Returning first middle node incorrectly
• Modifying list nodes accidentally

5. Suppose the linked list nodes can be reused multiple times in cycles (i.e., cycles can overlap or nest). Which modification to the fast-slow pointer approach correctly detects and counts the length of the first cycle encountered?

hard

A. Use a hash set to track visited nodes to detect cycles and count length, since fast-slow pointers fail with overlapping cycles.

B. Modify the fast pointer to move three steps at a time to detect overlapping cycles faster.

C. Run the fast-slow pointer detection multiple times from different starting points to find all cycles.

D. Use fast-slow pointers as usual; overlapping cycles do not affect detection of the first cycle.

Solution

1. Step 1: Understand overlapping cycles scenario

   Overlapping or nested cycles mean fast-slow pointers may not reliably detect all cycles or count lengths correctly.

2. Step 2: Evaluate approaches for correctness

   Using a hash set tracks all visited nodes, ensuring detection of any cycle and accurate length counting despite overlaps.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash set approach handles complex cycle structures correctly [OK]

Hint: Fast-slow pointers detect only simple cycles reliably [OK]

Common Mistakes:

• Assuming fast-slow pointers handle overlapping cycles
• Increasing fast pointer speed breaks correctness
• Multiple runs of fast-slow pointers are inefficient and incomplete