Detect and Break a Cycle in a Singly Linked List

Problem Statement

Given the head of a singly linked list, determine if the list contains a cycle. If a cycle exists, break it by setting the next pointer of the node that loops back to None (or null), and return the modified list's head. If no cycle exists, leave the list unchanged and return head.

You must solve this in O(n) time complexity and O(1) auxiliary space without modifying the values of any nodes.

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

Function Signature

def detect_and_remove_cycle(head: Optional[ListNode]) -> Optional[ListNode]:
    pass

Constraints

• The number of nodes in the list is in the range [0, 10^5].
• -10^9 <= ListNode.val <= 10^9
• Extra space must be O(1).

Examples

Example 1:

Input: head = [3, 2, 0, -4], pos = 1
# Node with value -4 points back to node with value 2 (0-indexed position 1)
Output: [3, 2, 0, -4]
# The next pointer of -4 is set to None, resulting in a standard null-terminated list.

Example 2:

Input: head = [1, 2], pos = 0
# Node 2 points back to node 1
Output: [1, 2]
# Node 2's next pointer is set to None.

Example 3:

Input: head = [1], pos = -1
# No cycle
Output: [1]

Edge Cases to Consider

• The list is empty (head is None) or contains only one node without a cycle.
• A single-node list pointing to itself (head.next == head).
• The cycle begins at the very first node (head).