Linked List Cycle II - Start of Cycle

📋

Problem

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

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

Edge cases: Empty list (head = null) → output: nullSingle node with no cycle → output: nullSingle node with cycle to itself → output: node itself

</>

IDE

def detectCycle(head: ListNode) -> ListNode:public ListNode detectCycle(ListNode head)ListNode* detectCycle(ListNode* head)function detectCycle(head)

def detectCycle(head):
    # Write your solution here
    pass

class Solution {
    public ListNode detectCycle(ListNode head) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

ListNode* detectCycle(ListNode* head) {
    // Write your solution here
    return nullptr;
}

function detectCycle(head) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: null when cycle existsFailed to reset slow pointer to head after cycle detection, so never found cycle start.✅ After detecting cycle, set slow = head and move slow and fast one step at a time until they meet.

Wrong: node with wrong value as cycle startIncorrect pointer movement after detection; moving pointers incorrectly or skipping steps.✅ Move both pointers exactly one step at a time after resetting slow to head until they meet.

Wrong: non-null for empty or single node no cycleNot handling base cases where head is null or single node with next null.✅ Add checks to return null immediately if head is null or no cycle detected.

Wrong: timeout on large inputUsing hash set or nested loops causing O(n^2) complexity.✅ Implement Floyd's cycle detection algorithm with two pointers for O(n) time and O(1) space.

✓

Test Cases

Try testing your solution on empty and single-node lists to handle edge cases.

Consider tricky cycle start positions and no-cycle scenarios to catch corner cases.

Optimize your solution to run in linear time and constant space for large inputs.

t1_01basic

Input{"head":[3,2,0,-4],"pos":1}

Expected2

⏱ Performance - must finish in 2000ms

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

💡 Use two pointers moving at different speeds to detect a cycle.

💡 Once a cycle is detected, reset one pointer to head and move both one step at a time to find the cycle start.

💡 Return the node where both pointers meet after resetting one to head.

Why it failed: Returned wrong node or null despite cycle; likely missed resetting slow pointer to head after detection. Fix by resetting slow to head and moving both pointers one step until they meet.

✓ Correctly detected cycle start node using Floyd's algorithm.

t1_02basic

Input{"head":[1,2],"pos":0}

Expected1

⏱ Performance - must finish in 2000ms

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

💡 Check if the fast pointer can catch up to the slow pointer to confirm a cycle.

💡 After detection, move one pointer to head and advance both pointers stepwise to find cycle start.

💡 Return the node where pointers meet, which is the cycle start.

Why it failed: Returned wrong node or null; possibly failed to handle cycle starting at head. Fix by resetting slow pointer to head after detection and moving both pointers one step until they meet.

✓ Correctly identified cycle start at head node.

t2_01edge

Input{"head":[],"pos":-1}

Expectednull

⏱ Performance - must finish in 2000ms

Empty list has no nodes and thus no cycle; output is null.

💡 Check if head is null before processing.

💡 If head is null, immediately return null as no cycle can exist.

💡 Add a base case to return null when head is None.

Why it failed: Returned non-null for empty list; fix by adding a check for null head at start and returning null immediately.

✓ Correctly handled empty list with no cycle.

t2_02edge

Input{"head":[1],"pos":-1}

Expectednull

⏱ Performance - must finish in 2000ms

Single node with no cycle returns null.

💡 Single node with next pointer null means no cycle.

💡 Ensure your cycle detection handles single node lists correctly.

💡 Return null if no cycle detected after traversal.

Why it failed: Returned non-null for single node without cycle; fix by ensuring cycle detection returns null if no cycle found.

✓ Correctly returned null for single node without cycle.

t2_03edge

Input{"head":[1],"pos":0}

Expected1

⏱ Performance - must finish in 2000ms

Single node with cycle to itself returns the node itself.

💡 Detect cycle even if list has only one node pointing to itself.

💡 Fast and slow pointers will meet at the single node.

💡 Return that node as the cycle start.

Why it failed: Returned null for single node cycle; fix by allowing detection when fast and slow pointers meet at the same single node.

✓ Correctly detected cycle starting at single node.

t3_01corner

Input{"head":[1,2,3,4,5],"pos":0}

Expected1

⏱ Performance - must finish in 2000ms

Cycle starts at head node; tests if algorithm correctly handles cycle at start.

💡 Check if cycle detection works when cycle starts at head.

💡 Reset slow pointer to head after detection and move both pointers stepwise.

💡 Return the node where pointers meet, which should be head.

Why it failed: Returned wrong node or null; likely failed to handle cycle starting at head. Fix by resetting slow pointer to head after detection and moving both pointers one step until they meet.

✓ Correctly identified cycle start at head node.

t3_02corner

Input{"head":[1,2,3,4,5,6],"pos":3}

Expected4

⏱ Performance - must finish in 2000ms

Cycle starts at node with value 4; tests if algorithm correctly finds cycle start in middle.

💡 Ensure pointers move correctly after cycle detection to find start node.

💡 Reset slow pointer to head and move both pointers one step at a time.

💡 Return the node where pointers meet, which is the cycle start.

Why it failed: Returned wrong node or null; likely failed to move pointers correctly after detection. Fix by resetting slow pointer to head and moving both pointers one step until they meet.

✓ Correctly found cycle start node in middle of list.

t3_03corner

Input{"head":[1,2,3,4,5],"pos":-1}

Expectednull

⏱ Performance - must finish in 2000ms

No cycle in list; tests if algorithm correctly returns null.

💡 If fast pointer reaches null, no cycle exists.

💡 Return null if no cycle detected after traversal.

💡 Avoid false positives by checking fast and fast.next pointers.

Why it failed: Returned non-null for no cycle; fix by returning null when fast or fast.next is null indicating no cycle.

✓ Correctly returned null for list with no cycle.

t4_01performance

Input{"head":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"pos":50}

Expected51

⏱ Performance - must finish in 2000ms

List of length 100 with cycle starting at node index 50; algorithm must run in O(n) time within 2 seconds.

💡 Use Floyd's cycle detection algorithm with two pointers.

💡 Avoid extra space by not using hash sets.

💡 Ensure O(n) time complexity by moving pointers efficiently.

Why it failed: Algorithm timed out due to O(n^2) or worse complexity; fix by implementing Floyd's cycle detection with O(n) time and O(1) space.

✓ Algorithm runs in O(n) time and passes performance test.

Practice

1. You are given a singly linked list and two integers M and N. The task is to traverse the list, skip M nodes, then delete the next N nodes, and repeat this process until the end of the list. Which algorithmic approach best guarantees an optimal O(n) time and O(1) space solution for this problem?

easy

A. Use a recursive approach that deletes nodes during the unwinding phase of recursion.

B. Use a brute force nested loop approach that for each node checks ahead to delete N nodes repeatedly.

C. Use an iterative two-pointer approach that skips M nodes and deletes N nodes in a single pass.

D. Use a dynamic programming approach to store states of nodes to decide deletion.

Solution

1. Step 1: Understand the problem constraints

   The problem requires skipping M nodes and deleting N nodes repeatedly until the list ends, which suggests a linear traversal.

2. Step 2: Evaluate approaches

   Recursive approaches add extra space due to call stack; brute force nested loops increase time complexity; dynamic programming is unnecessary as no overlapping subproblems exist. The iterative two-pointer approach efficiently traverses once, skipping and deleting nodes in O(n) time and O(1) space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Iterative two-pointer approach matches optimal time and space complexity [OK]

Hint: Iterative two-pointer approach is linear and space efficient [OK]

Common Mistakes:

• Thinking recursion is optimal despite extra stack space
• Using nested loops causing O(n²) time
• Misapplying DP to a linear traversal problem

2. Given the following Python code for reorderList and the input list 1->2->3->4, what is the value of the node pointed to by left after the first merge step in the recursion unwinding?

easy

A. Node with value 3

B. Node with value 2

C. Node with value 4

D. Node with value 1

Solution

1. Step 1: Trace recursion to the end

   Recursion reaches right = None, then unwinds from node 4 back to node 1.

2. Step 2: First merge step during unwinding

   At right=4, left=1, tmp=left.next=2; left.next=4; 4.next=2; left=2 after merge.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   After first merge, left points to node with value 2 [OK]

Hint: left moves forward after merging right node [OK]

Common Mistakes:

• Confusing left pointer update
• Off-by-one in recursion unwind
• Misreading next pointer assignments

3. Consider the following buggy code snippet for detecting a circular array loop. Which line contains the subtle bug that causes incorrect detection of single-element loops as valid cycles?

medium

A. Line with 'if nums[i] == 0: continue' - skipping zeros prematurely

B. Line with 'if slow == fast: return True' - missing check for single-element loop

C. Line with 'direction = nums[i] > 0' - direction assignment incorrect

D. Line with 'nums[slow] = 0' - zeroing visited elements too early

Solution

1. Step 1: Identify where single-element loops are checked

   The original code breaks if slow == next_index(slow) to avoid single-element loops.

2. Step 2: Locate missing check

   The buggy code returns True immediately when slow == fast without verifying cycle length.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing single-element loop check causes false positives [OK]

Hint: Check cycle length before returning True to avoid single-element loops [OK]

Common Mistakes:

• Returning True immediately on pointer meet
• Ignoring direction consistency
• Incorrectly zeroing elements

4. The following code attempts to detect a cycle in a circular array using the fast-slow pointer approach. Identify the line containing the subtle bug that causes incorrect cycle detection.

medium

A. Line with 'return true' inside while loop returns prematurely

B. Line with 'if slow == fast:' missing cycle length check

C. Line with 'direction = nums[i] > 0' incorrectly sets direction

D. Line with 'nums[marker] = 0' incorrectly marks visited elements

Solution

1. Step 1: Identify cycle detection condition

   The code returns true immediately when slow == fast, but does not check if cycle length > 1.

2. Step 2: Understand why self-loop is invalid

   Cycle of length 1 (self-loop) is invalid; must check if slow != next_index(slow) before returning true.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing cycle length check causes false positives [OK]

Hint: Check cycle length > 1 to avoid self-loop false positives [OK]

Common Mistakes:

• Returning true on self-loop cycles
• Mixing directions
• Not marking visited nodes

5. 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)