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.

Constraints:

• The number of the nodes in the list is in the range [0, 104].
• -105 <= Node.val <= 105
• 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: 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, reset the tortoise to the head. Move both the tortoise and hare 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) and a "hare" (fast). The tortoise moves one step at a time, while the hare moves two steps at a time. If there's a cycle, the hare will eventually lap the tortoise.

Finding the Cycle Start:

After detecting a cycle, we reset the tortoise to the head. We then move both the tortoise and hare one step at a time. The point at which they meet is the start of the cycle. This works because the distance from the head to the cycle start is equal to the distance from the meeting point to the cycle start (when traversing the cycle).

Code

using System;

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public ListNode DetectCycle(ListNode head) {
        // Floyd's Tortoise and Hare algorithm to detect cycle
        ListNode slow = head;
        ListNode 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 the start of the cycle
        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). We use only a constant amount of extra space for the pointers.