Linked List Cycle II medium

Problem Statement

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Constraints:

• The number of the nodes in the list is in the range [0, 10⁴].
• -10⁵ <= Node.val <= 10⁵
• pos is -1 or a valid index in the linked-list.

Example 1

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.

Example 2

Input: head = [1,2], pos = 0 Output: tail connects to node index 0 Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3

Input: head = [1], pos = -1 Output: None Explanation: There is no cycle in the linked list.

Steps and Explanation

The problem can be solved using Floyd's Tortoise and Hare algorithm. This algorithm consists of two pointers: a "slow" pointer (tortoise) and a "fast" pointer (hare).

1. Cycle Detection: The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If there is a cycle, the fast pointer will eventually lap the slow pointer. If they meet, a cycle exists.

2. Finding the Cycle Start: Once the cycle is detected, reset the slow pointer to the head of the list. Keep the fast pointer where it is (at the meeting point). Now, move both pointers one step at a time. The point where they meet again is the start of the cycle.

Why this works:

When the slow and fast pointers meet, let's say the slow pointer has traveled x steps and the fast pointer has traveled 2x steps. Let y be the distance from the start of the cycle to the meeting point. Let c be the length of the cycle. Then we have:

• x = a + y (where a is the distance from the head to the start of the cycle)
• 2x = a + y + nc (where n is the number of times the fast pointer has gone around the cycle)

Subtracting the first equation from the second:

x = nc - y

This means that the distance from the meeting point to the start of the cycle is y, which is also the distance from the head to the start of the cycle. Therefore, by moving both pointers at the same speed from the head and the meeting point, they will meet at the start of the cycle.

Code

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def detectCycle(head):
    """
    Finds the node where the cycle begins in a linked list.

    Args:
        head: The head of the linked list.

    Returns:
        The node where the cycle begins, or None if there is no cycle.
    """
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:  # Cycle detected
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow  # slow (and fast) now points to the cycle start
    return None  # No cycle


#Example usage
head = ListNode(3)
head.next = ListNode(2)
head.next.next = ListNode(0)
head.next.next.next = ListNode(-4)
head.next.next.next.next = head.next #create cycle

cycle_start = detectCycle(head)
if cycle_start:
    print(f"Cycle starts at node with value: {cycle_start.val}")
else:
    print("No cycle detected")


head2 = ListNode(1)
head2.next = ListNode(2)

cycle_start2 = detectCycle(head2)
if cycle_start2:
    print(f"Cycle starts at node with value: {cycle_start2.val}")
else:
    print("No cycle detected")

Complexity

• Time Complexity: O(N), where N is the number of nodes in the linked list. We traverse the list at most twice.
• Space Complexity: O(1). We use only a constant amount of extra space for the pointers.