Leetcode: Linked list cycle

Given the head of a linked list, determine if there is a cycle in the list. A cycle is defined as a chain of arbitrary length that point to the same node. As an added difficulty, the solution should have a space complexity of O(1). The first observation is that the cycle can be of arbitrary length. Thus, saving the visited nodes in a set would have a space complexity of O(n). Secondly, the numbers cannot be compared because numbers might be duplicated throughout the list. Instead, we need to compare the list objects themselves. The solution involves using two pointers with different step sizes. The first pointer, p1, has a step size of one and the second pointer, p2, has a step size of two. Then iterate as long as either one of the pointers (p2) reaches the end of the list or if both pointers point to the same object, in which case we found a loop.

from typing import Optional

# Definition for singly-linked list.
class ListNode:
  def __init__(self, x, n=None):
    self.val = x
    self.next = n

class Solution:
  def hasCycle(self, head: Optional[ListNode]) -> bool:
    if head is None:
      return False
    p1 = head
    p2 = head.next
    while p1 is not None and p2 is not None and p2.next is not None:
      if p1 == p2:
        return True
      p1 = p1.next
      p2 = p2.next.next
    return False


if __name__ == '__main__':
  s = Solution().hasCycle
  l = ListNode(2, ListNode(0, ListNode(-4)))
  l.next.next.next = l
  print(s(ListNode(3, l)), True)
  print(s(ListNode(1)), False)