Linked List Cycle II — LeetCode 142 Python Solution

The problem

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

Example

Input

head = [3,2,0,-4], pos = 1

Output

tail connects to node index 1

Explanation

There is a cycle in the linked list, where tail connects to the second node.

Python solution

# 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]:
        fast = slow = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                ans = head
                while ans != slow:
                    ans = ans.next
                    slow = slow.next
                return ans

Complexity

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 142. Linked List Cycle II is filed here because LeetCode tags it Linked List, which is the vocabulary this hub collects.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Related problems