Optimize Node.has_loop to use constant auxiliary space instead of O(N) space #15576

Feature description

Optimize has_loop to use constant auxiliary space

Description

The has_loop property in data_structures/linked_list/has_loop.py currently detects loops by traversing the linked list and storing every visited node in a set:

@property
def has_loop(self) -> bool:
    try:
        list(self)
        return False
    except ContainsLoopError:
        return True

The iterator uses:

visited = set()

and adds each visited node to that set. As a result, detecting whether a linked list contains a loop requires O(n) additional memory.

Proposed change

Update only the has_loop property in:

data_structures/linked_list/has_loop.py

Use Floyd’s tortoise-and-hare cycle-detection algorithm:

• A slow pointer moves one node at a time.
• A fast pointer moves two nodes at a time.
• If the pointers meet, the linked list contains a loop.
• If the fast pointer reaches the end of the list, no loop exists.

Expected complexity

Time complexity:  O(n)
Auxiliary space: O(1)

Required behavior

The updated has_loop property should correctly detect:

• an acyclic linked list;
• a self-loop;
• a loop back to an earlier node;
• a loop involving the final node;
• lists containing duplicate data values in different nodes.

Loop detection must compare node references rather than node data values.

Reference

Floyd’s cycle-finding algorithm