Linked List Cycle II

pos variable is used to:

  1. convert input array into linked list
  2. run unit test faster

This problem follows Linked List Cycle, which asks if there exists a cycle.

# Solution

# HashSet

Use HashSet st to store mappings from ListNode to index.


  • time: O(n)O(n)
  • space: O(n)O(n)
def detectCycle(self, head: ListNode) -> ListNode:
    st = set()
    curr = head
    while curr:
        if curr in st:
            return curr
            curr =
    return None

# Follow Up

Can you solve it using constant space?

# Floyd's Cycle-Finding Algorithm

solution at:

When slow and fast intersect, fast has traversed the cycle once and completed twice the distance of slow. So:

2distance(slow)=distance(fast)2⋅distance(slow) = distance(fast)
2(F+a)=F+a+b+a2(F+a) = F+a+b+a
2F+2a=F+2a+b2F+2a = F+2a+b
F=bF = b


  • time: O(n)O(n)
  • space: O(1)O(1)
def detectCycle(self, head: ListNode) -> ListNode:
    if not head or not return None
    slow = head
    fast = head
    while fast and
        slow =
        fast =
        if slow is fast: break
    if slow is not fast: return None

    # slow and fast intersect, cycle exists
    # now finds the cycle start
    ptr1 = head
    ptr2 = slow
    while ptr1!=ptr2:
        ptr1 =
        ptr2 =
    return ptr1
Last Updated: 7/19/2020, 3:45:14 PM