Given a linked list, determine if it has a cycle in it. A cycle is defined as having at least one node in the list whose next is the node itself.

Function Signature:

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

def has_cycle(head: ListNode) -> bool:
    """
    Determine if the linked list has a cycle.

    Parameters:
    - head: The head of the linked list.

    Returns:
    - bool: True if there is a cycle, False otherwise.
    """
    # Your code here

Example:

# Create a linked list with a cycle
head = ListNode(3)
head.next = ListNode(2)
head.next.next = ListNode(0)
head.next.next.next = ListNode(-4)
head.next.next.next.next = head.next  # Create a cycle
# Input: head = 3 -> 2 -> 0 -> -4
#                    ^          |
#                    |----------|
# Output: True 

# Create a linked list without a cycle
head_no_cycle = ListNode(1)
head_no_cycle.next = ListNode(2)
head_no_cycle.next.next = ListNode(3)
# Input: head_no_cycle = 1 -> 2 -> 3 -> None
# Output: False

Note:

  • The linked list may be modified, but the solution should use O(1) space.

Instructions:

  • Write the has_cycle function to solve the problem using fast and slow pointers.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊