Skip to main content

142. Linked List Cycle II

Tags:

Link

Floyd's algorithm

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:

        slow, fast = head, head

        cycle = False

        while fast and fast.next:

            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                cycle = True
                break

        if not cycle:
            return None

        fast = head

        # while fast:

        #     if fast == slow:
        #         return fast

        #     fast = fast.next
        #     slow = slow.next

        while slow != fast:
            fast = fast.next
            slow = slow.next

        return slow