Day 5: Fast and Slow pointers (Cycle detection)

Linked List Cycle

Linked List Tutorial

Recommended: Solution

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

def hasCycle(head):
        # If the list is empty, there is no cycle
        if not head:
            return False

        # Initialize two pointers, fast and slow
        # Fast moves 2 steps at a time and slow moves 1 step at a time
        fast = head.next
        slow = head.next

        # Loop until the fast pointer reaches the end of the list
        while fast and fast.next:
            # Move slow pointer by 1 step
            slow = slow.next
            # Move fast pointer by 2 steps
            fast = fast.next.next

            # If slow and fast meet, there's a cycle in the list
            if slow == fast:
                return True

        # If we exit the loop, fast reached the end of the list, hence no cycle
        return False        

Time Complexity = O(n)

Space Complexity = O(1)

If you have any questions, put them in the comment section. I will be glad to answer them!