Difficulty: Medium, Asked-in: Google, Amazon, Microsoft, Goldman Sachs, Nvidia

Key takeaway: An excellent linked list problem to learn problem-solving using fast and slow pointers. We can solve many other coding questions using the similar idea.

Let’s understand the problem

Given the head of a linked list, write a program to find if linked list has a cycle or not. Return true if there is a cycle, otherwise, return false.

A critical note related to the problem

In a singly linked list problem, we are mostly given link to the first node to perform basic operations like traversal, searching insertion, deletion, merging, etc. Algorithms for these operations require a well-formed linked list, i.e. linked list without loop or cycle.

The idea would be simple: A linked list with cycle causes iteration to fail because iteration will never reach the end. Therefore, detecting linked list with no cycle is desirable before applying some iterative approach.

If linked list has a cycle, then there is no end node, and one of its nodes is the next node of two nodes. So iterating through linked list will explore nodes present in the cycle multiple times.

Discussed solution approaches

•  Brute force approach using hash table
• Using boolean flag inside linked list node
• An efficient approach  using fast and slow pointers

 Brute force approach using hash table

Solution idea

The basic idea is to traverse the linked list and store visited nodes in a hash table. During this process, there is a cycle if we encounter any visited nodes again. Otherwise, if we reach the end of the linked list, there is no cycle.

Solution steps

Step 1: We define a hash table to store linked list nodes.

Step 2: We traverse the linked list using loop until currNode != NULL.

• We first search currNode in the hash table. If currNode is already present, we return true. Otherwise, we insert currNode in the hash table and move to the next node.

Step 3: When currNode == NULL, we return false. It means, we have reached the end, and there is no cycle in the linked list.

Solution pseudocode

class ListNode
{
    int data
    ListNode next
}

bool detectLinkedListLoop(ListNode head)
{
    HashTable <ListNode> H
    ListNode currNode = head
    while (currNode != NULL)
    {
        if (H.search(currNode) == true)
            return true
        H.insert(currNode)  
        currNode = currNode->next
    }
    return false
}

Time and space complexity analysis

Only one traversal of linked list is needed in the above code. In other words, algorithm will perform only one insert and search operation for each node. So time complexity = n*O(1) =O(n). We are using a hash table for storing linked list nodes, so space complexity = O(n)

Using boolean flag inside linked list node

Solution idea

Can we optimise above approach by avoiding the overhead of hash table operations? The idea would be to add an extra flag visited in the structure of linked node. This could help us mark the visited nodes and identify their duplicate presence. Note: Initially, visited flag is 0 for each node.

We traverse linked list using a loop. During this process, we mark visited field as 1 whenever a node is visited for the first time. There is a cycle if we again encounter a node with visited flag 1.

Solution pseudocode

class ListNode
{
    int data
    ListNode next
    int visited = 0
}

bool detectLinkedListLoop(ListNode head)
{
    ListNode curr = head  
    while (curr != NULL)
    {
        if (curr->visited == 1)
            return true
        curr->visited == 1
        curr = curr->next
    }
    return false
}

Time and space complexity analysis

It is working in O(n) time complexity as the algorithm is traversing each node once. We are using an extra variable with each node, so space complexity = O(n)

An efficient approach using fast and slow pointers

Solution idea

The above solutions use O(n) space, so the critical question is: Can we optimize further and detect linked list cycle using O(n) time and O(1) space?

The optimized solution idea is based on Floyd’s cycle finding algorithm that uses two pointers at different speeds i.e. fast and slow. At each step of iteration, slow pointer moves 1 step while the fast pointer moves two steps. Note: This algorithm is also called tortoise and the hare algorithm.

Solution steps

Step 1: We initialize two pointers fast and slow with head node.

Step 2: Now we run a loop to traverse the linked list. At each step of iteration, we move slow pointer by one position and fast pointer by two positions.

• If fast pointer reach the end (fast == NULL or fast->next == NULL), then there is no loop in the linked list.
• Otherwise, the fast and slow pointers keep moving in the cycle and meet at some point. So this means: there is a loop in the linked list. The critical question is: Why will this happen? 

One basic intuition is simple: Suppose two people are moving in a circular track at different speeds. After some point in time, a fast person definitely will meet the slow person.

Solution pseudocode

class ListNode
{
    int data
    ListNode next
}

bool detectLinkedListLoop(ListNode head)
{
    ListNode slow = head
    ListNode fast = head
    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next
        fast = fast->next->next
        if (slow == fast)
            return true
    }
    return false
}

Here are some critical observations, when there is a cycle of length l in the linked list.

Fast pointer is moving two times the speed of slow pointer. So gap between both pointers will increases by one after every iteration. For example, after 5th iteration, fast pointer will move 10 steps and slow pointer will move 5 steps. Gap between them = 10 - 5 = 5

When slow pointer just enters the loop, fast pointer will be already present inside the loop. Suppose at this point, fast pointer is at distance k from slow pointer (k < l).

Now both pointers will start moving in the loop and gap between them will keep increasing by 1 after each iteration. When this gap becomes l, both pointers will meet because they are moving in a cycle of length l. So total steps travelled by both pointers in cycle before meeting at some common point = l - k.

Time and space complexity analysis

Suppose for the analysis purpose :

• Total number of nodes in linked list = n
• The length of linked list cycle (if any) = l
• The distance of the cycle's starting point from beginning = m. Here l + m = n
• When slow pointer enters the loop, fast pointer distance from the slow pointer = k.

Case 1: When there is no loop in linked list, fast pointer will reach the end after n/2 steps. Time complexity = O(n)

Case 2: When there is a loop in linked list.

Both pointers will move m steps before slow pointer take entry into the loop. Inside the loop, both pointers will travel (l - k) steps before meeting at some common point. Time complexity = Total number of steps traveled by both pointers from start to meeting at common point = m + (l - k) = l + m - k = n - k (equation 1).

If slow pointer travel m distance from start to reach the bridge point, then fast pointer will travel 2m distance from the start. There will be two cases:

When m < l: k = m and total steps travelled by both pointers before meeting at a common point = n - k = n - m (From equation 1). So time complexity in the worst case = O(n), where the worst-case scenario occurs when m = 1.

When m >= l: In this situation, fast pointers will first move m distance to reach the bridge point and revolve m/l times in the cycle. So the distance of fast pointer from the bridge point (k) = m mod l 

Total no of steps travelled by both pointers before meeting at the common point = n - k = n - m mod l (From equation 1). So time complexity in the worst case = O(n), where worst-case scenario occurs when m = l.

Overall, time complexity would be O(n) in the worst case. The algorithm is working in constant space, space complexity = O(1)

Critical ideas to think!

• How do we modify the above approaches to remove the loop?
• Design an algorithm to find the loop length in the linked list.
• If there is a loop in the linked list, what would be the best-case scenario of the fast and slow pointer approach?
• How do we find the bridge node if there is any loop present?
• Can we solve this problem using some other approach?
• Is it necessary to move the fast pointer with double speed? What will happen if we move the fast pointer with speed four times the slow pointer?

Comparison of time and space complexities

•  Using a hash table: Time = O(n), Space = O(n)
• Using linked list augmentation: Time = O(n), Space = O(n)
• Floyd’s cycle detection algorithm: Time = O(n), Space = O(1)

Suggested problems to practice

• Remove loop from the linked list 
• Return the node where the cycle begins in a linked list
• Swap list nodes in pairs
• Reverse a linked list in groups of a given size
• Intersection point in Y shaped linked lists

Enjoy learning, Enjoy algorithms!