Friedrich Ewald My Personal Website

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)
Runtime: 112 ms, faster than 15.44% of Python3 online submissions for Linked List Cycle. Memory Usage: 17.6 MB, less than 67.21% of Python3 online submissions for Linked List Cycle.


About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.