141

141. Linked List Cycle

First demonstration of using a fast and slow pointer when traversing a linked list. We’re asked to determine if a linked list has a cycle in it. Using two pointers, with one going faster than the other by traversing two .next calls, if the slow and fast pointers ever collide, we know there is a cycle.

If the fast pointer ever reaches None, we know that the linked list is not cyclic.

The solution is as follows:

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head
 
        while slow and fast:
            fast = fast.next
            if fast: fast = fast.next
            if slow == fast: return True
            slow = slow.next
 
        return False

_ Time Complexity:

O(n) - We traverse all nodes within the linked list.

_ Space Complexity:

O(1) - We maintain two pointers, slow and fast.