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 need to find the node that is exactly in the middle of the list. Which approach guarantees finding the middle node in a single pass with constant extra space?

easy

A. Store all nodes in an array, then access the middle index directly.

B. Traverse the list twice: first to count nodes, second to reach the middle node.

C. Use two pointers: move one pointer twice as fast as the other; when the fast pointer reaches the end, the slow pointer is at the middle.

D. Use a recursive approach to reach the end and count backwards to the middle.

Solution

1. Step 1: Understand the problem constraints

   The goal is to find the middle node in a single pass and O(1) space.

2. Step 2: Identify the approach that uses two pointers

   Using a slow pointer moving one step and a fast pointer moving two steps ensures when fast reaches the end, slow is at the middle.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two-pointer technique is classic for single-pass middle node [OK]

Hint: Two pointers with different speeds find middle in one pass [OK]

Common Mistakes:

• Thinking counting then traversing is single pass
• Using extra space unnecessarily
• Recursion adds overhead and is not optimal

2. You are given a singly linked list and need to determine if it reads the same forwards and backwards. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Use fast and slow pointers to find the middle, reverse the second half in-place, then compare both halves.

B. Convert the linked list to an array and check palindrome by comparing elements from both ends.

C. Use a hash set to store visited nodes and check for palindrome by comparing values.

D. Use a recursive approach to compare nodes from start and end simultaneously.

Solution

1. Step 1: Identify the problem constraints

   The problem requires checking palindrome in O(n) time and O(1) space.

2. Step 2: Evaluate approaches

   Converting to array uses O(n) space, recursion uses O(n) stack space, and hash set is not suitable for palindrome check. Using fast and slow pointers to reverse second half in-place meets both time and space requirements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Optimal approach uses fast-slow pointers and in-place reversal [OK]

Hint: Optimal palindrome check uses fast-slow pointers and in-place reversal [OK]

Common Mistakes:

• Assuming array conversion is optimal due to simplicity
• Believing recursion uses constant space
• Using hash sets for palindrome detection

3. 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

4. Consider the following buggy code snippet for reorderList. Which line contains the subtle bug that can cause infinite loops or cycles when traversing the reordered list?

medium

A. Line with 'if left == right or left.next == right:' missing 'right.next = None' termination

B. Line with 'if not right: return' -- base case missing

C. Line with 'if stop: return' -- premature termination

D. Line with 'left = tmp' -- left pointer not updated correctly

Solution

1. Step 1: Identify termination condition

   The code must set right.next = None when left meets right or adjacent to avoid cycles.

2. Step 2: Locate missing termination

   The commented line misses 'right.next = None', causing the list to form cycles.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing termination causes infinite traversal [OK]

Hint: Always terminate reordered list with null to avoid cycles [OK]

Common Mistakes:

• Forgetting to set right.next = null
• Misplacing stop flag
• Incorrect pointer updates

5. Suppose the problem is modified so that the array elements can be zero, representing no movement, and cycles of length 1 (self-loop) are now considered valid. Which modification to the original fast and slow pointer algorithm correctly handles this variant?

hard

A. Remove the check that breaks when slow == next_index(slow), allowing single-element loops to return True.

B. Add a condition to skip zeros in the outer loop and treat zero jumps as invalid for cycles.

C. Modify the direction check to allow zero as both positive and negative direction to include zero jumps.

D. Use a visited set to track indices and return True if any index is revisited, ignoring direction.

Solution

1. Step 1: Understand new problem constraints

   Zero jumps are allowed and single-element loops are valid cycles.

2. Step 2: Identify necessary algorithm change

   The original code breaks when slow == next_index(slow) to exclude single-element loops; removing this check allows detecting single-element cycles.

3. Step 3: Confirm direction and zero handling

   Zeros represent no movement; allowing them means direction check must still be consistent, but zero jumps can form valid cycles.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Removing single-element loop break correctly detects new valid cycles [OK]

Hint: Allow single-element loops by removing cycle length >1 check [OK]

Common Mistakes:

• Skipping zeros entirely
• Treating zero as both directions
• Ignoring direction consistency