DAY 93 - Floyd Cycle Detection Algorithm. Finding a Cycle in a Linked List

Hey Guys! Today is Day 93 and this side Nayan. Today we will be covering Floyd's Cycle Detection Algorithm also known as Floyd's Tortoise and Hare Algorithm.

We will be covering today what is the algorithm through the question Finding a cycle in linked list and the intuition behind this and how do we approach it.

Let's understand our question first:

Question: Leetcode 141. Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

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.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Question Breakdown and Intuition:

• To be precise the question is asking us if there is an element in our linked list which points back to an element in the linked list making it a cycle.
• The first thing that our mind should hit is a hashMap approach. If we can store the nodes and their respective count values, after traversing the linked list, eventually we will reach a same node again and find out that it contains a cycle.
• Although this approach is optimal in time complexity we are using an extra O(N) space which is not good.
• So how can we optimize this, that's where the Floyd's Cycle Detection Algorithm comes in:

Floyd's Cycle Detection Algorithm:

The idea behind the algorithm is that, if you have two pointers in a linked list, one moving twice as fast (the hare) than the other (the tortoise), then if they intersect, there is a cycle in the linked list. If they don't intersect, then there is no cycle.

Let's go back to our question and try if we can actually solve it with this:

Code + Breakdown:

• I'll first declare to Node Pointers namely slow and fast representing our tortoise and hare respectively.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

bool hasCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
}

• I will then check if our given linked list is non existent(basically head == null) or only contains one element(head->next == NULL). In such case we shall return our head as there will exist no cycle in any such case.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

 bool hasCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        if(head == NULL) return false;
        if(head ->next == NULL) return false;
}

• Now that we have made the preparations let's start traversing in the linked list. We will check at any point if our fast pointer points to null or if it's next is null so that we don't go out of linked list.

• We will initialize a while loop here with conditions that our fast pointer or fast->next does not point to null.

• We will move our slow pointer by one times ahead and our fast pointer by two times ahead.

• We shall then check if after this movement our fast and slow (hare and tortoise) are at the same position then we return true because in a linked list which was straight they shall never meet.
  

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

bool hasCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        if(head == NULL) return false;
        if(head ->next == NULL) return false;
        while(fast != NULL && fast->next != NULL){

            slow = slow->next;
            fast = fast->next->next;
            if(fast == slow) return true;
        }

        return false;
    }

Visual Representation:

Code Complexity Analysis:

Time Complexity:

• Traversing of linked list at least one time leads to O(N) complexity where N is length of linked list.

• Overall, the time complexity is O(N).

Space Complexity

• Only use pointers slow and fast to solve the problem hence only constant space added.

• Overall, the space complexity is O(1).