Problem 5 - Linked list cycle

Question

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

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.

Approach

This solution uses Floyd's Tortoise and Hare algorithm (also sometimes referred to as slow and fast pointer algorithm) to detect and find the start of a cycle in a linked list. It involves two phases:

1. Finding if a cycle exists - In this phase, two pointers (slow and fast) move through the linked list at different speeds. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If there is a cycle in the linked list, the fast pointer will eventually catch up to the slow pointer. This is because the fast pointer moves twice as fast as the slow pointer, so it will eventually loop around and meet the slow pointer inside the cycle. If there is no cycle, the fast pointer will reach the end of the list.

2. Finding the start of the cycle - Once the fast and slow pointers meet, we know that a cycle exists in the linked list. To find the start of the cycle, we reset the slow pointer back to the head of the linked list, while keeping the fast pointer at the meeting point. Both the slow and fast pointers now move one step at a time until they meet again. The meeting point will be the start of the cycle.

Solution

This question is often presented as a two-part question - detect if a cycle exists and find where the cycle begins.

public class Solution {
    public ListNode detectCycle(ListNode head) {
        // No cycle if the list is empty or contains only one node
        if (head == null || head.next == null) {
            return null;
        }
        
        // Both slow and fast pointer initially points to the head
        ListNode slow = head;
        ListNode fast = head;
        boolean hasCycle = false;
        
        // Move slow and fast pointers until they meet or reach the end of the list
        while (fast != null && fast.next != null) {
            slow = slow.next; // slow pointer one step at a time
            fast = fast.next.next; // fast pointer two steps at a time
            
            if (slow == fast) {
                // Both pointers met inside the loop, cycle exists
                hasCycle = true;
                break;
            }
        }
        
        if (!hasCycle) {
            return null;
        }
        
        // Reset slow pointer to the head of the list
        slow = head;
        
        // Move both pointers one step at a time until they meet again
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        
        // The meeting point is the start of the cycle
        return slow;
    }
}

Time and space complexity

Time Complexity: The time complexity of the above solution is O(n), where n is the number of nodes in the linked list. This is because both phases of the algorithm require traversing the linked list at most once.

Space Complexity: The space complexity of the solution is O(1) because it uses a constant amount of additional space, regardless of the size of the input linked list.