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 nullptr.

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. Note that pos is not passed as a parameter.

Notice that you should 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: null Explanation: There is no cycle in the linked list.

Steps

1. Cycle Detection: Use Floyd's Tortoise and Hare algorithm to detect if a cycle exists. This involves two pointers, one moving one step at a time (tortoise) and the other moving two steps at a time (hare). If a cycle exists, they will eventually meet.

2. Finding the Cycle Start: Once the cycle is detected, reset the tortoise to the head of the list. Keep the hare where it met the tortoise. Move both pointers one step at a time. The point where they meet again is the start of the cycle.

Explanation

Floyd's Tortoise and Hare: The algorithm's brilliance lies in the fact that when the hare and tortoise meet, they have traversed a total distance that is a multiple of the cycle length. This is because the hare moves twice as fast.

Finding the Cycle Start: Let's say the distance from the head to the cycle start is x, and the cycle length is c. When the tortoise and hare meet, the hare has traveled twice the distance of the tortoise. Let k be an integer representing the number of times the hare has completed a cycle. Then:

x + k * c + y = 2(x + y) where y is the distance from the cycle start to the meeting point.

Simplifying, we get: x = (k-1)*c + y. This means that if we start the tortoise at the head and the hare at the meeting point and move them one step at a time, they will meet at the start of the cycle after x steps.

Code

#include <iostream>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode *detectCycle(ListNode *head) {
    if (head == nullptr || head->next == nullptr) return nullptr;

    ListNode *slow = head;
    ListNode *fast = head;

    // Detect cycle
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }

    // No cycle
    if (fast == nullptr || fast->next == nullptr) return nullptr;

    // Find cycle start
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }

    return slow;
}

int main() {
    // Example usage (you can modify this to test different inputs)
    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 = detectCycle(head);
    if (cycleStart != nullptr) {
        std::cout << "Cycle starts at node with value: " << cycleStart->val << std::endl;
    } else {
        std::cout << "No cycle detected." << std::endl;
    }

    //Clean up memory (important to avoid memory leaks)
    ListNode* current = head;
    ListNode* next;
    while(current != nullptr){
        next = current->next;
        delete current;
        current = next;
    }

    return 0;
}

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). The algorithm uses only a constant amount of extra space.