C++: Linked List Cycle II

Thought Process

To detect the starting node of a cycle in a linked list, we use Floyd's Tortoise and Hare algorithm. First, we determine if a cycle exists by using a slow pointer and a fast pointer. If they meet, a cycle is confirmed. Then, we reset a entry pointer to the head and move both the entry pointer and the slow pointer one step at a time until they meet. The meeting point is the starting node of the cycle. 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        
        ListNode *slow = head;
        ListNode *fast = head;
        ListNode *entry = head;

        while(fast!=NULL && fast->next !=NULL){

            slow = slow->next;
            fast = fast->next->next;

            if(slow==fast){

                while(entry!=slow){
                    entry = entry->next;
                    slow = slow->next;
                }
                return slow;
            }
        }
        return NULL;

    }
};

Code Complexity

Time Complexity: O(n)

The algorithm iterates through the linked list once, making it linear in time complexity.

Space Complexity: O(1)

The algorithm uses only three pointers, ensuring constant space usage.

Code copied!