< Back




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.