142. Linked List Cycle II

Description

Given the head of a linked list, the task is to determine if the linked list contains a cycle. If a cycle exists, return the node where the cycle begins. If there is no cycle, return null.

Intuition

To detect a cycle in a linked list, we can use Floyd's Tortoise and Hare algorithm. This algorithm uses two pointers that move at different speeds through the list. If there is a cycle, the fast pointer will eventually meet the slow pointer. To find the entry point of the cycle, we move one pointer to the head and keep the other at the meeting point. Both pointers then move one step at a time until they meet again at the cycle's entry point.

Approach

1. Initialize Two Pointers: Start with two pointers, slow and fast, both pointing to the head of the list.
2. Move Pointers: Move the slow pointer one step at a time and the fast pointer two steps at a time.
3. Detect Cycle: If the fast pointer reaches the end of the list, there is no cycle. If the slow pointer meets the fast pointer, a cycle is detected.
4. Find Cycle Start: Move one pointer to the head of the list and keep the other at the meeting point. Move both pointers one step at a time. The node where they meet is the start of the cycle.

Complexity

Time Complexity:

O(N), where N is the number of nodes in the linked list. In the worst case, we traverse the list twice: once to detect the cycle and once to find the cycle's starting node.

Space Complexity:

O(1), since we only use two pointers and no additional data structures.

Code

C++

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == nullptr) return nullptr;
        
        ListNode *slow = head;
        ListNode *fast = head;

        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                while (fast != head) {
                    head = head->next;
                    fast = fast->next;
                }
                return head;
            }
        }
        return nullptr;
    }
};

Python

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None

        slow, fast = head, head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                while fast != head:
                    head = head.next
                    fast = fast.next
                return head

        return None

Java

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;

        ListNode slow = head;
        ListNode fast = head;

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

JavaScript

var detectCycle = function(head) {
    let slow = head;
    let fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast) {
            while (fast !== head) {
                head = head.next;
                fast = fast.next;
            }
            return head;
        }
    }
    return null;
};