starting point of the cycle

Given a linked list, we have to return the node where the cycle begins. If there is no cycle, return NULL. and pos is not passed as a parameter.

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

 

method:

Determine whether there is a cycle:

 Using a slow(s) pointer that move forward 1 step each time

Using a fast (f) pointer that move forward 2 steps each time

If the slow pointer and fast pointer both point to the same location after several moving steps, there is a cycle;

Otherwise, if (fast== NULL || fast->next== NULL), there has no cycle.

If there is a cycle, return the starting point:

till slow/fast (which are pointing at the same node ) is not equal to head ,move slow/fast and head by one step.

now when slow== head return head

c++ implementation:

ListNode *detectCycle(ListNode *head) {
         ListNode *f=head;
         ListNode *s=head;
        
        while(f!=NULL && f->next!=NULL)
        {
            f=f->next->next;
            s=s->next;
            if(f==s)
                break;
        }
        if(f==NULL||f->next==NULL)
            return NULL;
        if(head==s)
            return head;
        while(head!=s)
        {
            head=head->next;
            s=s->next;
        if(s==head)
                return head;
        }
    return NULL;
    }

Time Complexity: O(n)  
space Complexity: O(1)