142. Linked List Cycle II

Explain

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.

Note:

Do not modify the linked list.

Solve

# 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

Performance

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.