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 null.

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.

Do not modify 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: null Explanation: There is no cycle in the linked list.

Steps:

1. Detect Cycle: Use Floyd's Tortoise and Hare algorithm to detect if a cycle exists. If no cycle is found, return null.
2. Find Cycle Start: Once a cycle is detected, use two pointers: one starting at the head and the other at the meeting point of the tortoise and hare. Move both pointers one step at a time. The point where they meet is the start of the cycle.

Explanation:

Floyd's Tortoise and Hare Algorithm (Cycle Detection):

This algorithm uses two pointers, a "tortoise" (slow pointer) and a "hare" (fast pointer). The tortoise moves one step at a time, while the hare moves two steps at a time. If there is a cycle, the hare will eventually lap the tortoise.

Finding the Cycle Start:

After detecting a cycle, we know the distance from the head to the cycle start is equal to the distance from the meeting point to the cycle start, going around the cycle once. By starting one pointer at the head and another at the meeting point and moving them one step at a time, they will meet at the cycle's start.

Code:

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.next = (next===undefined ? null : next)
    }
}

function detectCycle(head: ListNode | null): ListNode | null {
    // Floyd's Tortoise and Hare Algorithm
    let slow = head;
    let fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow!.next;
        fast = fast.next.next;
        if (slow === fast) { // Cycle detected
            break;
        }
    }

    // No cycle
    if (fast === null || fast.next === null) {
        return null;
    }

    // Find cycle start
    slow = head;
    while (slow !== fast) {
        slow = slow!.next;
        fast = fast!.next;
    }

    return slow;
}

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). The algorithm uses only a constant amount of extra space.