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, 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: 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 Entry: 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 entry point of the cycle.

Explanation:

Floyd's Tortoise and Hare: This algorithm uses two pointers, one moving one step at a time (tortoise), and the other moving two steps at a time (hare). If there's a cycle, the hare will eventually overtake the tortoise.

Finding the Cycle Entry: Let's say the distance from the head to the cycle entry is a, the length of the cycle is b, and the distance from the meeting point to the cycle entry is c. When the hare overtakes the tortoise, the hare has traveled a distance of a + b + c + kb (where k is some integer number of cycle laps), and the tortoise has traveled a + c. Since the hare travels twice as fast, we have:

2(a + c) = a + b + c + kb

Solving for a:

a = (k-1)b + c

This means that if we start one pointer at the head and another at the meeting point, and move them both one step at a time, they will meet at the cycle entry after a steps.

Code:

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

public class LinkedListCycleII {
    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 cycle entry
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        // Example Usage
        LinkedListCycleII solution = new LinkedListCycleII();
        ListNode head = new ListNode(3);
        head.next = new ListNode(2);
        head.next.next = new ListNode(0);
        head.next.next.next = new ListNode(-4);
        head.next.next.next.next = head.next; // Create cycle

        ListNode cycleStart = solution.detectCycle(head);
        if (cycleStart != null) {
            System.out.println("Cycle starts at node with value: " + cycleStart.val);
        } else {
            System.out.println("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 pointers.