Technical Interview Question

You are given a singly linked list. Write a function to determine if the linked list contains a cycle. A cycle is defined as any node in the linked list that has its next pointer point to a previously visited node. The function should return true if a cycle exists and false otherwise.

Signature:

def hasCycle(head: ListNode) -> bool:

Example

Input:

head = 3 -> 2 -> 0 -> 4
         ^         |
         |         |
          ----------

Output:

True

Explanation

To determine if the linked list has a cycle, we can use the "Floyd's Tortoise and Hare Algorithm", also known as the "Hare and Tortoise Algorithm". The algorithm uses two pointers, one slow and one fast, that move through the linked list at different speeds.

1. Initialize two pointers, slow and fast, both at the head of the linked list.
2. Iterate through the linked list using the following rules:
   • Move the slow pointer one step at a time.
   • Move the fast pointer two steps at a time.
   • If the fast pointer reaches the end of the linked list (i.e., it encounters a None value), there is no cycle, and we can return False.
   • If the slow and fast pointers meet at any point during the iteration, it indicates the presence of a cycle, and we can return True.

By moving the pointers at different speeds, if the linked list contains a cycle, the fast pointer will eventually reach the slow pointer.

Here is the implementation in Python:

def hasCycle(head: ListNode) -> bool:
    # Initialize pointers
    slow = head
    fast = head
    
    # Iterate through the linked list
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        # If pointers meet, there is a cycle
        if slow == fast:
            return True
    
    # No cycle found
    return False

The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list.