Detect Cycles in a Linked List

This challenge focuses on a fundamental data structure problem: detecting cycles within a linked list. Identifying cycles is crucial in various applications, such as preventing infinite loops in data processing, analyzing network structures, and understanding memory management in certain programming languages. Your task is to implement an efficient algorithm to determine if a given linked list contains a cycle.

Problem Description

You are given the head of a singly linked list. Your goal is to write a Python function that returns True if the linked list contains a cycle, and False otherwise.

A cycle exists in a linked list if any node in the list can be reached again by continuously following the next pointer. This means that at some point, a node's next pointer will point back to a node that has already been visited.

Key Requirements:

• Implement a function has_cycle(head) that takes the head of a linked list as input.
• The function should return a boolean value: True if a cycle is detected, False otherwise.
• You should assume the existence of a ListNode class (or similar structure) with at least a val attribute (for the node's value) and a next attribute (pointing to the next node or None).

Expected Behavior:

• If the linked list is empty (head is None), it contains no cycle.
• If the linked list has a single node and its next is None, it contains no cycle.
• If a node's next pointer eventually leads back to a previously visited node, a cycle is present.

Edge Cases:

• An empty list.
• A list with a single node.
• A list where the cycle involves the first node (e.g., node1.next = node1).
• A list with a long chain before entering a cycle.

Examples

Example 1:

Input: A linked list representing [3, 2, 0, -4] where the node with value -4 points back to the node with value 2.
The linked list structure would be:
head -> 3 -> 2 -> 0 -> -4
        ^--------------|

Output: True

Explanation: The node with value -4 has its next pointer pointing to the node with value 2, creating a cycle.

Example 2:

Input: A linked list representing [1, 2] where the node with value 2 points to None.
The linked list structure would be:
head -> 1 -> 2 -> None

Output: False

Explanation: The linked list terminates with None, so there is no cycle.

Example 3:

Input: A linked list representing [1] where the node with value 1 points to itself.
The linked list structure would be:
head -> 1 --^
      |_____|

Output: True

Explanation: The single node's next pointer points back to itself, forming a cycle.

Constraints

• The number of nodes in the linked list can be between 0 and 10⁴.
• The value of each node is an integer.
• The next pointer of a node is either None or points to another node in the list.
• Your solution should 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 track visited nodes. A common and efficient solution for this problem uses two pointers moving at different speeds. Think about how the relative movement of these pointers can reveal the presence of a cycle.