Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Do not modify the linked list.
# Definition for singly-linked list. class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def detectCycle(self, head: ListNode) -> ListNode: l1 = l2 = head while l2 and l2.next: l1 = l1.next l2 = l2.next.next if l1 == l2: l1 = head while l1 != l2: l1 = l1.next l2 = l2.next return l2 return None
Runtime: 60 ms, faster than 62.74% of Python3 online submissions for Linked List Cycle II.
Memory Usage: 16.8 MB, less than 100.00% of Python3 online submissions for Linked List Cycle II.