Linked List Cycle

Our solution detects whether a linked list contains a cycle by employing the Floyd's Tortoise and Hare algorithm. This algorithm uses two pointers, slow and fast, which traverse the linked list at different speeds.

1. Initialization: Both slow and fast pointers start at the head of the linked list.
2. Traversal:
   • Slow Pointer: Moves one step at a time (slow = slow->next).
   • Fast Pointer: Moves two steps at a time (fast = fast->next->next).
3. Detection:
   • If at any point the slow pointer and fast pointer meet, it indicates the presence of a cycle in the linked list. This is because the fast pointer will loop around and eventually catch up with the slow pointer if a cycle exists.
   • If the fast pointer reaches the end of the list (fast == nullptr or fast->next == nullptr), then there is no cycle in the list.

The algorithm is efficient as it only requires a single pass through the list with constant space complexity. It is straightforward and avoids the need for extra data structures.

Time Complexity: The solution has a time complexity of O(n), where n is the number of nodes in the linked list. This is because the slow and fast pointers will traverse the list at most once each, making the traversal efficient.

Space Complexity: The solution has a space complexity of O(1) since it uses only two pointers and does not require additional space proportional to the input size. This makes the algorithm both space and time efficient.