Linked List Cycle III

Problem: Linked List Cycle III – Remove Cycle

While LeetCode does not have a dedicated "Linked List Cycle III" problem, the task is commonly given in interviews:

Given a singly linked list that contains a cycle, detect and remove the cycle by modifying the .next pointer of the last node in the cycle to null.

Intuition

Once a cycle is detected using Floyd's algorithm, we can:

• Find the starting node of the cycle.

• Traverse the cycle until we find the node that points back to the starting node.

• Set that node’s .next = null to break the cycle.

Steps

1. Detect cycle using Floyd's Tortoise and Hare algorithm.

2. Find the start of the cycle.

3. Traverse from the cycle start to locate the last node in the cycle.

4. Break the cycle by setting the last node’s .next = null.

Java Code: Remove Cycle in Linked List

class Solution {
    public void removeCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        // Step 1: Detect cycle
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (slow == fast) {
                break;
            }
        }

        // Step 2: If no cycle, return
        if (fast == null || fast.next == null) return;

        // Step 3: Find start of cycle
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        // Step 4: Find the last node in the cycle and break it
        ListNode start = slow;
        ListNode ptr = start;
        while (ptr.next != start) {
            ptr = ptr.next;
        }

        // Break the cycle
        ptr.next = null;
    }
}

Dry Run Example

List: 1 → 2 → 3 → 4 → 5 → 6
                      ↑    ↓
                      ← ← ←
Cycle at node with value 3

• Floyd’s algorithm detects the cycle at some meeting point.

• Reset one pointer to head; move both pointers one step at a time to find the start of the cycle (node 3).

• Traverse the cycle until you find the last node that points to node 3 (node 6).

• Set node6.next = null to break the cycle.

Time and Space Complexity

Conclusion

This builds directly on cycle detection (LeetCode 141) and finding the cycle’s start (LeetCode 142). It's a practical extension that tests your ability to modify linked structures based on pointer logic.