142.Linked List Cycle II

Qns Link: https://leetcode.com/problems/linked-list-cycle-ii/

Let’s solve another leetcode problem in this article which is a famous and most frequently asked problem in big tech companies like META , google.

Prerequisite: Kindly read my article on linked list where I explained why we are going with linked list over array and also explained Floyd’s algorithm (Fast and Slow pointer) which gives the clear view about fast and slow pointer.

If you had read my earlier article you know that we always focus on thought process i.e what they asked us to do rather than directly getting into the solution part. Let’s continue that streak here also,

Cycle (https://www.interviewbit.com/blog/wp-content/uploads/2021/12/Image-3.gif)

Let’s breakdown the problem , in this problem they will give us with linked list and asked us to detect whether there is a cycle or not if so then return the node where the cycle starts and they also asked to solve without modifying the linked list.

Let’s get ourself understand with the example given in the leetcode.

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.

We have to return the node 2 since the cycle starts there.

Steps:

👊First detect whether cycle exist or not if so proceed or else return NULL.

👊Find the length of the cycle.

👊With that Cycle length , we can find the start of the cycle.

Now, let’s see how to do,

By using fast and slow pointer, let’s find whether cycle is there or not.

Initially fast=slow=head

If fast pointer moves 2 step ahead then slow pointer moves 1 step ahead. If Cycle exists, then at one point both the fast and slow meets. Let’s prove this by running this approach in the above given example.

Iterate until the fast !=null and fast.next!=null

“Consider the below numbers as their address”

1st iteration: slow=3 , fast=3

2nd iteration: slow=2 , fast=0

3rd iteration: slow=0 , fast=2

4th iteration: slow=-4 , fast=-4

Now both the slow and fast points to the same address hence there exist a cycle , then use that slow pointer(or fast pointer) to find the length of the cycle.

Now , let’s find the length of the cycle ,

Now store that slow (or fast pointer) where it satisfies fast = slow in the temporary variable. And iterate temp until it reach the slow pointer. Thus we find the length of the Cycle.

In our case the slow pointer(or fast pointer) is 4.Iterate until it reaches 4 again. I showed the code below to find the cycle length.

public int cycleLength(ListNode node){
                ListNode temp=node;
                int len=0;
                do{
                    temp=temp.next;
                    len++;
                }
                while(temp!=node);
                return len;
}

Now we found the length of the cycle.

The only part that left is to find the start of the cycle. Let’s solve that now, again use two pointer but not fast and slow pointer. Instead use normal pointers. Initially move one the pointers until the length becomes 0 with help of looping statement.

Then move another pointer(let it be the second pointer) until the the first pointer becomes equal to the that pointer. At one stage the first and the second pointer becomes equal that is where the cycle begins.

In our case the length of the cycle is 3. Initially first=3 and second =3 ,move the fast pointer 3 times, then it will be in 4.

1st iteration: first=2 , second=2 now both first and second pointers are same. Now return 2 which is the start of the cycle.

That’s it 🔥. We are done. We found the start of the cycle. This is the thought process behind solving this problem.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {

        public int cycleLength(ListNode node){
                ListNode temp=node;
                int len=0;
                do{
                    temp=temp.next;
                    len++;
                }
                while(temp!=node);
                return len;
    }
    public ListNode detectCycle(ListNode head) {
        int length=0;
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(slow==fast){
                length=cycleLength(fast);
                break;
            }
        }

        if(length==0){
            return null;
        }
        //find the first and second

        ListNode first=head;
        ListNode second=head;
        while(length>0){
            first=first.next;
            length--;
        }
        while(first!=second){
            first=first.next;
            second=second.next;
        }
        return first;
    }
}

Try the above program and get to understand about the flow using the debug pointers.

If you find any value in this article, consider FOLLOWING me! Thanks 😇

#LearnInPublic #HappyCoding