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. Consider the following Python function that deletes N nodes after skipping M nodes in a linked list. Given the linked list 1 -> 2 -> 3 -> 4 and parameters M=1, N=1, what is the linked list after calling delete_n_after_m_optimized(head, 1, 1)?

easy

A. 1 -> 3 -> 4

B. 2 -> 3 -> 4

C. 1 -> 2 -> 4

D. 1 -> 4

Solution

1. Step 1: Trace skipping M=1 node

   Starting at node 1, skip 1 node means stay at node 1 (loop runs zero times).

2. Step 2: Delete N=1 node after current

   Delete node after 1, which is node 2. So, link node 1's next to node 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Resulting list is 1 -> 3 -> 4 after deletion [OK]

Hint: Skipping M=1 means no move; delete next N=1 node [OK]

Common Mistakes:

• Off-by-one in skipping nodes
• Deleting wrong nodes after skipping
• Misunderstanding loop ranges

2. Given the following code for finding the middle node of a linked list, what is the value returned when the input list is 1 -> 2 -> 3 -> 4?

easy

A. 2

B. 3

C. 4

D. 1

Solution

1. Step 1: Trace slow and fast pointers

   Initial: slow=1, fast=1; Iteration 1: slow=2, fast=3; Iteration 2: fast.next is null, loop ends.

2. Step 2: Return slow's value

   Slow points to node with value 3 at loop end.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   For even length, returns second middle node (3) [OK]

Hint: Fast pointer moves twice as fast; slow ends at middle [OK]

Common Mistakes:

• Returning first middle node for even length
• Off-by-one errors in loop condition
• Confusing slow and fast pointer positions

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

4. Identify the bug in the following code snippet for detecting and returning the cycle length in a linked list.

medium

A. Line 11: The length counting loop should start with length = 0 instead of 1.

B. Line 6: slow pointer should move two steps instead of one.

C. Line 7: fast pointer should move one step instead of two.

D. Line 4: The condition should check both fast and fast.next to avoid null pointer errors.

Solution

1. Step 1: Check loop condition for pointer safety

   The loop condition only checks if fast is not null, but fast.next may be null causing runtime error on fast.next.next.

2. Step 2: Confirm other lines are correct

   Slow moves one step, fast moves two steps correctly; length counting starts at 1 correctly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing fast.next check causes null pointer dereference [OK]

Hint: Always check fast and fast.next before advancing fast by two steps [OK]

Common Mistakes:

• Forgetting fast.next check
• Off-by-one in length counting
• Swapping slow and fast pointer steps

5. Suppose you want to find the middle node of a linked list, but the list is circular (the last node points back to the head). Which modification to the two-pointer approach correctly finds the middle node without infinite looping?

hard

A. Use the same two-pointer approach but add a visited set to detect cycles and stop when fast pointer revisits a node.

B. Use recursion to count nodes until the head is reached again, then find middle by index.

C. Convert the circular list to a linear list by breaking the cycle first, then apply the standard two-pointer approach.

D. Modify the loop to stop when fast or fast.next equals the head node, then return slow pointer.

Solution

1. Step 1: Understand circular list behavior

   In a circular list, fast pointer will loop infinitely unless we detect when it cycles back to head.

2. Step 2: Modify loop condition

   Stop when fast or fast.next equals head to avoid infinite loop; slow pointer will be at middle.

3. Step 3: Compare alternatives

   Visited set adds extra space; breaking cycle modifies input; recursion risks stack overflow.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Stopping at head detects cycle end without extra space [OK]

Hint: Detect cycle by checking if fast pointer returns to head [OK]

Common Mistakes:

• Using visited set wastes space
• Breaking cycle modifies input
• Recursion risks stack overflow