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)  



darkmode