Detect Linked List Cycle

A linked list is a fundamental data structure in computer science. Understanding how to manipulate and analyze them is crucial. One common problem is determining if a linked list contains a cycle, meaning a node points back to a previously visited node, creating an infinite loop. This skill is valuable for debugging and optimizing algorithms that utilize linked lists.

Problem Description

Your task is to write a function that takes the head of a singly linked list as input and determines if there is a cycle within the list. A cycle exists if any node in the list can be reached again by continuously following the next pointer.

Requirements:

• The function should return True if a cycle is detected, and False otherwise.
• You should not modify the original linked list structure.
• You should aim for an efficient solution in terms of time and space complexity.

Expected Behavior:

• If the linked list is empty or has only one node with no self-loop, it does not contain a cycle.
• If a node's next pointer eventually leads back to that same node or any preceding node, a cycle is present.

Edge Cases:

• An empty linked list (head is null).
• A linked list with a single node that points to itself (a self-loop).
• A linked list with multiple nodes where the cycle starts at the head.
• A linked list with multiple nodes where the cycle starts at a later node.
• A very long linked list without a cycle.

Examples

Example 1:

Input: A linked list where node 1 -> node 2 -> node 3 -> node 2 (cycle)
       head points to node 1.
       (Node structure: { value: ..., next: ... })
Output: True
Explanation: Node 3's next pointer points back to node 2, creating a cycle.

Example 2:

Input: A linked list where node 1 -> node 2 -> node 3 -> null
       head points to node 1.
Output: False
Explanation: The list terminates at node 3 with a null pointer, so no cycle exists.

Example 3:

Input: A linked list where node 1 -> node 1 (self-loop)
       head points to node 1.
Output: True
Explanation: Node 1's next pointer points to itself, forming a cycle.

Constraints

• The number of nodes in the linked list can range from 0 to 10⁵.
• The value of each node is an integer. (This constraint is for context, but your solution should not depend on the values themselves.)
• The solution should ideally have a time complexity of O(n) and a space complexity of O(1), where 'n' is the number of nodes in the linked list.

Notes

Consider different approaches to solving this problem. One common and efficient method involves using two pointers that traverse the list at different speeds. Think about how the relative movement of these pointers can indicate the presence of a cycle.