LeetCode 142: Linked List Cycle II

Explanation

To detect a cycle in a linked list and find the node where the cycle begins, we can use Floyd's Tortoise and Hare algorithm. This algorithm involves two pointers moving at different speeds through the linked list. If there is a cycle, the two pointers will eventually meet at some point within the cycle.

1. Initialize two pointers, slow and fast, both starting at the head node.
2. Move the slow pointer by one node and the fast pointer by two nodes at each iteration.
3. If the two pointers meet at a certain node, there is a cycle in the linked list.
4. Move one pointer back to the head node and then move both pointers at the same pace until they meet again. The node where they meet is the starting point of the cycle.

The time complexity of this algorithm is O(n) where n is the number of nodes in the linked list. The space complexity is O(1) since we are using only two pointers.

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }

        return null;
    }
}