Remove Loop in Linked List

Remove Loop in Linked List

Problem Statement

Given a linked list. If the linked list contains a loop, return True and remove the loop.
A linked list contains a cycle if it consists of a node that can be reached again by continuously following the next pointer.


Output: 1 -> 2 -> 3 -> 4 -> 5
Explanation: The linked list consists of a loop, where the last node connects to the second node. Hence, remove the loop

Output: 1 -> 2

Approach: Using HashSet

The simplest approach to solve this problem is to check whether a node in the linked list has been visited before. To perform this operation, a hashmap can be used. If a node has already occurred before, simply set the current pointer to NULL.


  • Initialise a hashmap.
  • Traverse the linked list till the head pointer isn’t NULL:
    • If the current node is already present in the hashmap, it ensures that the linked list contains a loop. Hence, set the node to NULL.
    • Else, continue traversing and continue inserting the node into the hashset.
  • If no node satisfy the above conditions, then the linked list does not contain any cycle.

C++ Implementation

void hashAndRemove(Node * head) {
  unordered_map < Node * , int > node_map;
  Node * last = NULL;
  while (head != NULL) {
    if (node_map.find(head) == node_map.end()) {
      last = head;
      head = head -> next;
    } else {
      last -> next = NULL;

Java Implementation

 static boolean removeLoop(Node h)
        HashSet<Node> s = new HashSet<Node>();
        Node prev = null;
        while (h != null) {
            if (s.contains(h)) {
       = null;
                return true;
            else {
                prev = h;
                h =;
        return false;

Python Implementation

def removeLoop(head):
        mp = set()
        prev = NULL
        while head is not None:
            if head in mp:
       = NULL
                return True
                prev = head
                head =
        return False

Time Complexity:O(N) where N is the number of nodes of the linked list.
Space Complexity:O(N), as HashSet is used

Efficient Approach: Using Floyd’s Cycle Detection Algorithm

This approach uses a two-pointer – a fast pointer and a slow pointer to determine if there exists a cycle in the loop. The slow pointer moves one node ahead at a time, while the fast pointer moves two nodes ahead at a time.

If a loop exists in the linked list, the fast and slow pointers are bound to meet at some point.


  • Initialise two pointers, fast and slow to the head of the linked list.
  • Traverse through the linked list until the fast pointer doesn’t reach the end of the linked list.
  • If the fast pointer reaches the end, it means that the linked list doesn’t contain any cycle. Hence, return False.
  • Else, move the slow pointer by one node i.e. slow = slow -> next and fast pointer by two nodes i.e. fast = fast -> next -> next.
  • At any point, if the fast and the slow pointers point to the same node, set node-> next = NULL and return True as a loop has been detected.

C++ Code

void removeCycle(Node * slow, Node * head) {
  for (Node * curr = head; curr != nullptr; curr = curr -> next) {
    Node * ptr = slow;
    while (ptr -> next != slow && ptr -> next != curr) {
      ptr = ptr -> next;
    if (ptr -> next == curr) {
      ptr -> next = nullptr;
Node * identifyCycle(Node * head) {
  Node * slow = head, * fast = head;
  while (fast && fast -> next) {
    slow = slow -> next;
    fast = fast -> next -> next;
    if (slow == fast) {
      return slow;
  return nullptr;

Java Code

public static void removeCycle(Node slow, Node head) {
  for (Node curr = head; curr != null; curr = {
    Node ptr = slow;
    while ( != slow && != curr) {
      ptr =;
    if ( == curr) { = null;
public static Node identifyCycle(Node head) {
  Node slow = head, fast = head;
  while (fast != null && != null) {
    slow =;
    fast =;
    if (slow == fast) {
      return slow;
  return null;

Python Code

def removeCycle(slow, head):
    curr = head
    while curr:
        ptr = slow
        while is not slow and is not curr:
            ptr =
        if == curr:
   = None
        curr =
def identifyCycle(head):
    slow = fast = head
    while fast and
        slow =
        fast =
        if slow == fast:
            return slow
    return None

Time Complexity:O(N), where N is the number of nodes of the linked list.
Space Complexity:O(1), as a map is used.


Q. How do you detect a loop in a linked list?
A. A loop can be detected efficiently using the fast and slow pointer algorithm, where the fast pointer moves by two nodes and the slow pointer move by one node at a time. Read more here

Q. Will the fast and slow pointer always meet at some point if the list contains a cycle?
A. Yes, if the linked list contains a cycle, the fast and slow pointer will always meet at some point.

Previous Post
Strassen's Matrix Multiplication

Strassen’s Matrix Multiplication

Next Post
Applications of IoT

Top Major IoT Applications