Detect and remove loop in a linked list

Problem Statement: Given the head of a linked list, determine if the linked list has a cycle in it and remove it.

Examples:

Input:



Output: Cycle exists.

The final linked list is as follows after removing the loop:

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

We can divide this problem into three sub-problems:

Detecting a cycle in linked list
Starting point of the cycle in linked list
Removing the cycle in linked list

Let’s solve each sub-problem one by one and combine to get the final solution

Solution 1:

Approach: BruteForce Approach

We can use hashing. Following steps are involved in this approach:

Traverse every node in the linked list and insert them in the hashtable.
Maintain a prev pointer which keeps the track of previous nodes..
If a node is already present in the hashtable, this indicates that the loop is present.
To break the loop, make the next pointer of the prev pointer to point to NULL.

Let’s understand this approach from the code given below

Code:

C++ Code

#include<iostream>
#include<unordered_set>
using namespace std;

struct node {
  int data;
  node * next;
  node(int d) {
    data = d;
    next = NULL;
  }
};
void loopDetDelBrute(node * head) {
  unordered_set < node * > uns;

  node * prev = NULL;
  node * current = head;
  while (current != NULL) {
    if (uns.find(current) != uns.end()) { // loop detected
      prev -> next = NULL; // breaking the loop
      return;
    }
    uns.insert(current);

    prev = current;
    current = current -> next;
  }
}
// for checking if our approach works
bool FLD(node * head) {
  node * slow = head;
  node * fast = head;

  while (fast != NULL && fast -> next != NULL) {
    slow = slow -> next;
    fast = fast -> next -> next;
    if (slow == fast) return true;
  }
  return false;
}
int main() {
  node * head = new node(15);
  head -> next = new node(10);
  head -> next -> next = new node(12);
  head -> next -> next -> next = new node(20);
  head -> next -> next -> next -> next = head -> next;
  loopDetDelBrute(head);
  FLD(head) ? cout << "Loop Detected" : cout << "Loop not detected";
}

Time complexity: O(n)

Space complexity: O(n)

Java Code

import java.util.HashSet;
import java.util.Set;

class node {
  int data;
  node next;
  node(int d) {
    data = d;
    next = null;
  }
}

class Main {

  public static void main(String args[]) {
    node head = new node(15);
    head.next = new node(10);
    head.next.next = new node(12);
    head.next.next.next = new node(20);
    head.next.next.next.next = head.next;
    loopDetDelBrute(head);
    if (FLD(head)) {
      System.out.println("Loop Detected");
    } else System.out.println("Loop not detected");
  }
  
  static void loopDetDelBrute(node head) {
    Set < node > set = new HashSet < > ();
    node prev = null;
    node current = head;
    while (current != null) {
      if (set.contains(current)) // loop detected
      {
        prev.next = null; // loop removal
        return;
      }
      set.add(current);

      prev = current;
      current = current.next;
    }

  }
  // for checking if our approach is correct
  public static boolean FLD(node head) {
    node slow = head;
    node fast = head;
    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
      if (slow == fast) return true;
    }
    return false;
  }
}

Time complexity: O(n)

Space complexity: O(n)

Solution 2:

Approach: Better Approach

In this approach, we count the number of nodes in the loop and then perform the necessary operations to remove the loop.

Use Floyd’s cycle detection algorithm to check for the cycle.
Now, we count the number of nodes (x) which are a part of the loop.
Now, we use two pointers, one placed at the head node and other placed at xth node from the head.
Now we move both the pointers at the same speed and wherever they meet, that would be the starting node of our loop.
Now we point the last node of the loop to NULL.

Let’s check the code for this approach for a better understanding

Code:

C++ Code

#include<iostream>
using namespace std;

struct node {
  int data;
  node * next;
  node(int d) {
    data = d;
    next = NULL;
  }
};
void loopDetDelBetter(node * head) {
  // step 1
  node * slow = head, * fast = head;
  while (fast != NULL && fast -> next != NULL) {
    slow = slow -> next;
    fast = fast -> next -> next;
    if (slow == fast) break; // first meeting point
  }
  if (slow != fast) return;

  node * ptr1 = slow;
  node * ptr2 = slow;

  // step 2
  int x = 1;
  while (ptr2 -> next != ptr1) {
    ptr2 = ptr2 -> next;
    x++;
  }

  // step 3
  ptr1 = head; // move one pointer to head

  // move one pointer to xth node from head
  ptr2 = head;
  for (int i = 0; i < x; i++) {
    ptr2 = ptr2 -> next;
  }

  // step 4
  while (ptr1 != ptr2) {
    ptr1 = ptr1 -> next;
    ptr2 = ptr2 -> next;
  }

  // step 5
  while (ptr2 -> next != ptr1) {
    ptr2 = ptr2 -> next;
  }
  ptr2 -> next = NULL;
}
// to check if our approach is correct
bool FLD(node * head) {
  node * slow = head;
  node * fast = head;

  while (fast != NULL && fast -> next != NULL) {
    slow = slow -> next;
    fast = fast -> next -> next;
    if (slow == fast) return true;
  }
  return false;

}
int main() {
  node * head = new node(15);
  head -> next = new node(10);
  head -> next -> next = new node(12);
  head -> next -> next -> next = new node(20);
  head -> next -> next -> next -> next = head -> next;
  loopDetDelBetter(head);
  FLD(head) ? cout << "Loop Detected" : cout << "Loop not detected";
}

Time Complexity: O(n)

Space Complexity: O(1)

Java Code

class node {
  int data;
  node next;
  node(int d) {
    data = d;
    next = null;
  }
}

class Main {

  public static void main(String args[]) {
    node head = new node(15);
    head.next = new node(10);
    head.next.next = new node(12);
    head.next.next.next = new node(20);
    head.next.next.next.next = head.next;
    loopDetDelBetter(head);
    if (FLD(head)) {
      System.out.println("Loop Detected");
    } else System.out.println("Loop not detected");
  }

static void loopDetDelBetter(node head) {
    // step 1
    node slow = head;
    node fast = head;

    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
      if (slow == fast) {
        break;
      }
    }
    if (slow != fast) return;

    node ptr1 = slow;
    node ptr2 = slow;

    // step 2
    int x = 1;
    while (ptr2.next != ptr1) {
      ptr2 = ptr2.next;
      x++;
    }

    // step 3
    ptr1 = head; // move one pointer to head
    ptr2 = head;
    for (int i = 0; i < x; i++) {
      ptr2 = ptr2.next; // move one pointer to xth node from head;
    }

    // step 4
    while (ptr1 != ptr2) {
      ptr1 = ptr1.next;
      ptr2 = ptr2.next;
    }

    // step 5
    while (ptr2.next != ptr1) {
      ptr2 = ptr2.next;
    }
    ptr2.next = null;
  }
  public static boolean FLD(node head) {
    node slow = head;
    node fast = head;
    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
      if (slow == fast) return true;
    }
    return false;
  }
}

Time Complexity: O(n)

Space Complexity: O(1)

Solution 3:

Approach: Optimal Approach

In this approach, we don’t count the number of nodes in the loop

Following are the steps to be performed while implementing this approach

Use floyd detection cycle to detect the cycle in the linked list
Move the slow pointer to the head node.
Now move the fast and the slow pointer with the same speed.
Wherever they meet, that is the starting node of the cycle.
Change the next pointer of the previous node to point to NULL thus breaking the cycle present in the linked list.

Let’s check the execution of this approach

Code:

C++ Code

#include<iostream>
using namespace std;

struct node {
  int data;
  node * next;
  node(int d) {
    data = d;
    next = NULL;
  }
};

void loop_detection_deletion(node * head) {

  // Floyd Loop Detection Algorithm
  node * slow = head, * fast = head;
  while (fast != NULL && fast -> next != NULL) {
    slow = slow -> next;
    fast = fast -> next -> next;
    if (slow == fast) break; // first meeting point
  }
  if (slow != fast) return;

  // Loop Removal Algorithm
  slow = head;
  // locating the starting node of the loop
  while (slow -> next != fast -> next) {
    slow = slow -> next;
    fast = fast -> next;
  }
  // terminating the loop
  fast -> next = NULL;
}
bool FLD(node * head) {
  node * slow = head;
  node * fast = head;

  while (fast != NULL && fast -> next != NULL) {
    slow = slow -> next;
    fast = fast -> next -> next;
    if (slow == fast) return true;
  }
  return false;

}
int main() {
  node * head = new node(15);
  head -> next = new node(10);
  head -> next -> next = new node(12);
  head -> next -> next -> next = new node(20);
  head -> next -> next -> next -> next = head -> next;
  loop_detection_deletion(head);
  FLD(head) ? cout << "Loop Detected" : cout << "Loop not detected";
}

Time Complexity: O(n)

Space Complexity: O(1)

Java Code

class node {
  int data;
  node next;
  node(int d) {
    data = d;
    next = null;
  }
}

class Main {

  public static void main(String args[]) {
    node head = new node(15);
    head.next = new node(10);
    head.next.next = new node(12);
    head.next.next.next = new node(20);
    head.next.next.next.next = head.next;
   loopDetDelOptimal(head);
    if (FLD(head)) {
      System.out.println("Loop Detected");
    } else System.out.println("Loop not detected");
  }

  static void loopDetDelOptimal(node head) { // Floyd Cycle Detection Algorithm
    node slow = head;
    node fast = head;

    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
      if (slow == fast) {
        break;
      }
    }
    if (slow != fast) return;

    // Loop Removal Algorithm
    slow = head;
    // checking for intersection of two pointers
    while (slow.next != fast.next) {
      slow = slow.next;
      fast = fast.next;
    }
    // loop termination
    fast.next = null;
  }

  public static boolean FLD(node head) {
    node slow = head;
    node fast = head;
    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
      if (slow == fast) return true;
    }
    return false;
  }
}

Time Complexity: O(n)

Space Complexity: O(1)

In the above code under loop removal algorithm, we see that we are not checking for equality between slow and fast pointers but rather checking for the equality between the next of the slow and the fast pointers. This is done because we need to get the hold of the last node from where we’ll break the loop.

We could do this either way by maintaining the reference to the previous node and then changing the next pointer of the previous node to point to NULL.

We can see the following images to get a better understanding of the algorithm.

After loop detection, we move our slow pointer to the head and then move both slow and the fast pointers at the same speed and check if the next pointer of the slow and fast pointer are the same.

In this case, the next pointer of both slow and fast pointers are the same, so we are changing the next pointer of fast to point to NULL.

For more understanding of how to detect loops in the linked list, refer to this article.

Special thanks to Yash Mishra for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article