Linked List Cycle II
pos variable is used to:
- convert input array into linked list
- run unit test faster
This problem follows Linked List Cycle, which asks if there exists a cycle.
st to store mappings from
ListNode to index.
def detectCycle(self, head: ListNode) -> ListNode: st = set() curr = head while curr: if curr in st: return curr else: st.add(curr) curr = curr.next return None
# Follow Up
Can you solve it using constant space?
# Floyd's Cycle-Finding Algorithm
fast has traversed the cycle once and completed twice the distance of
def detectCycle(self, head: ListNode) -> ListNode: if not head or not head.next: return None slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next 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 = ptr1.next ptr2 = ptr2.next return ptr1