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.

Examples:
Input:

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.

Algorithm

• 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()) {
      node_map[head]++;
      last = head;
      head = head -> next;
    } else {
      last -> next = NULL;
      break;
    }
  }
}

Java Implementation

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

Python Implementation

def removeLoop(head):
        mp = set()
        prev = NULL
        while head is not None:
            if head in mp:
                prev.next = NULL
                return True
            else:
                mp.add(head)
                prev = head
                head = head.next
        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.

Algorithm

• 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;
      return;
    }
  }
}
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 = curr.next) {
    Node ptr = slow;
    while (ptr.next != slow && ptr.next != curr) {
      ptr = ptr.next;
    }
    if (ptr.next == curr) {
      ptr.next = null;
      return;
    }
  }
}
public static Node identifyCycle(Node head) {
  Node slow = head, fast = head;
 
  while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) {
      return slow;
    }
  }
  return null;
}

Python Code

def removeCycle(slow, head):
    curr = head
    while curr:
        ptr = slow
        while ptr.next is not slow and ptr.next is not curr:
            ptr = ptr.next
 
        if ptr.next == curr:
            ptr.next = None
            return
 
        curr = curr.next
 
 
def identifyCycle(head):
    slow = fast = head
 
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        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.

FAQs

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.