How to find and remove loops in a Linked List?

Question

Given a Linked List, how can you detect and remove a loop from that linked list efficiently?

Sample Test Cases:

Test Case 1

Sample Input

Expected Output 13-->24-->26-->38-->41-->NULL.

Test Case 2

Sample Input

Expected Output

55-->45-->54-->63-->56-->NULL

Test Case 3

Sample Input

Expected Output

7-->9-->8-->6-->NULL

Explanation

As the problem states, we need to find a loop in a LinkedList and remove it. If the loop was found and successfully removed, return true and print the list after removing the loop else, if the loop was not found, return false. For example, the linked list in sample test case 1, after removing the loop should change to 13-->24-->26-->38-->41-->NULL. Before removing the loop, it is important to detect it. To detect the loop we use Floyd’s Cycle detection algorithm. To remove the loop, the pointer to the last node of the loop is required which is node 41 in the above test case. After having the pointer to the last node of the loop, we just need to set its next pointer to null. After detecting the loop, there are different methods to approach this problem. We have discussed them below.

Naive Approach

• Floyd’s Cycle Detection Algorithm will stop when fast and slow pointers meet at a common point.
• This common point will be one of the nodes that are part of the loop.
• Store the address of this common point in a node variable named loopNode.
• Later, start from the head node of the Linked List and check whether any one of all nodes is reachable from loopNode one by one.
• Each time a reachable node will be found, that node will be the start node of the loop in the Linked List and the pointer to the node that is previous to this node can be found.

Java Code

import java.lang.*;
import java.util.*;
 //LinkedListClass and Node class
class List {
 
    static Node head;
 
    static class Node {
 
        int data;
        Node next;
 
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
 
     //detect loop in the list
    int detectLoop(Node node)
    {
        Node slow = node, fast = node;
        while (slow != null && fast != null
               && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            // If slow and fast meet at the same point then a loop is there return 1;
            if (slow == fast) {
                removeLoop(slow, node);
                return 1;
            }
        }
        //else return 0
        return 0;
    }
 
    // remove loop
    void removeLoop(Node loop, Node curr)
    {
        Node head = null, loopNode = null;
 
        /* move the pointer to the beginning of the Linked List
         one by one  */
        head = curr;
        while (true) {
 
            /* Now start a pointer from node where they meet and check
             if it ever reaches  loopNode*/
            loopNode = loop;
            while (loopNode.next != loop && loopNode.next != head) {
                loopNode = loopNode.next;
            }
 
            /* If loopNode reached head then there is a loop. So
             break it */
            if (loopNode.next == head) {
                break;
            }
 
            // If loopNode didn't reach head then try the next node after head 
            head = head.next;
        }
 
        /* After the end of the loop loopNode is the last node of the loop. So make next of loopNode as NULL */
        loopNode.next = null;
    }
 
    //  print the linked list
    void print(Node node)
    {
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
         List list = new List();
        list.head = new Node(13);
        list.head.next = new Node(24);
        list.head.next.next = new Node(26);
        list.head.next.next.next = new Node(38);
        list.head.next.next.next.next = new Node(41);
 
        // testing by creating a loop
         head.next.next.next.next.next = head.next.next;
        list.detectLoop(head);
        System.out.println(
            "Linked List after removing loop : ");
        list.print(head);
    }
}

Output Screenshot

Python Code

class Node:
    # Constructor for node object
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    # initialize head
    def __init__(self):
        self.head = None

    def detectLoop(self):
        slow = fast = self.head
        while(slow and fast and fast.next):
            slow = slow.next
            fast = fast.next.next

            # If slow and fast meet 
            # then there is a loop
            if slow == fast:
                self.removeLoop(slow)
                # Return 1 to indicate that loop if found
                return 1
 
        # Return 0 to indicate that there is no loop
        return 0
 
    # Function to remove loop
    # loop node= Pointer to loop node
    # head = Pointer to the start node of the linked list
    def removeLoop(self, loop_node):
        
        head = self.head
        while(1):
            # Now start a pointer from loop_node and check
            # if it ever reaches loopnode
            loopnode = loop_node
            while(loopnode.next != loop_node and loopnode.next != head):
                loopnode = loopnode.next
 
            # If loopnode reached head then there is a loop.
            # So break the loop
            if loopnode.next == head:
                break
            head = head.next
 
        # After the end of loop loopnode is the last node of
        # the loop. So make next of loopnode as NULL
        loopnode.next = None

    # insert a new node at the beginning
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node
 
    # function to print the linked LinkedList
    def printL(self):
        temp = self.head
        while(temp):
            print (temp.data)
            temp = temp.next
 
 
# Driver code
llist = LinkedList()
llist.push(13)
llist.push(24)
llist.push(26)
llist.push(38)
llist.push(41)

# Create a loop for testing
llist.head.next.next.next.next.next = llist.head.next.next
 
llist.detectLoop()
 
print ("after removing loop")
llist.printL()

Output Screenshot

C++ Code

#include <bits/stdc++.h>
using namespace std;
 
/* list node */
struct Node {
    int data;
    struct Node* next;
};
 
/* Function to remove loop.
Used by detectLoop() */
void removeLoop(struct Node*, struct Node*);
 
/* This function detects and
  removes loop in the list*/
int detectLoop(struct Node* list)
{
    struct Node *slow = list, *fast = list;
 
    while (slow && fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
 
        /* If slow and fast meet then
           there is a loop */
        if (slow == fast) {
            removeLoop(slow, list);
 
            /* Return 1 : loop is found */
            return 1;
        }
    }
 
    /* Return 0 :there is no loop*/
    return 0;
}
 
/* Function to remove loop.
 loop_node : Points to
 one of the loop nodes
 head : Points to the
 start node of the list */
void removeLoop(struct Node* loop_node, struct Node* head)
{
    struct Node* loopNode;
    struct Node* curr;
 
    /* Move the pointer to the beginning
      Linked List and move it one position at a time
      to get the
      first node */
    loopNode = head;
    while (1) {
        /* Now start a pointer from
        loop_node and check if
       it ever reaches ptr2 */
        curr = loop_node;
        while (curr->next != loop_node
               && curr->next != loopNode)
            curr = curr->next;
 
        /* If curr reached loopNode
        then a loop is there. So
        break it */
        if (curr->next == loopNode)
            break;
 
        /* If curr didn't reach loopNode
         then try the next node
         * after loopNode */
        loopNode = loopNode->next;
    }
 
    /*  at the end, curr will be the last node of the loop. So make next of curr as NULL */
    curr->next = NULL;
}
 
/*  print linked list */
void printL(struct Node* node)
{
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
}
 
struct Node* newNode(int key)
{
    struct Node* temp = new Node();
    temp->data = key;
    temp->next = NULL;
    return temp;
}
 
// Driver Code
int main()
{
    struct Node* head = newNode(13);
    head->next = newNode(24);
    head->next->next = newNode(26);
    head->next->next->next = newNode(38);
    head->next->next->next->next = newNode(41);
 
    head->next->next->next->next->next = head->next->next;
 
    detectLoop(head); 
    cout << " List after removing loop" << endl; 
    printL(head);
    return 0;

Output Screenshot

Time Complexity

The time complexity for this code is O(n^2) where n is the number of nodes in the Linked List. It is O(n^2) because, for every node of the Linked List, we have to traverse the entire Linked List to check if that node is reachable from the loop node.

Space Complexity

The space complexity of this code is O(1) because we are not using any additional space or data structure to store the values.

Efficient Method

• The first step of this method is the same, use Floyd’s Cycle Detection Algorithm to detect loop and get the pointer to a node belonging to the loop.

• Count the number of nodes in the loop and set the count to c.
• Set a pointer at the head and another at c’th node from the head.
• Move both the pointers at equal speed, they will meet at the starting node of the loop.
• Get the pointer to the last node of the loop and set its next pointer to null.

Java Code

class LinkedList {

    static Node head;
 
    static class Node {
 
        int data;
        Node next;
 
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
 
    // detect loop in the list
    int detectLoop(Node node)
    {
        Node slow = node, fast = node;
        while (slow != null && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
 
            // If  loop is present
            if (slow == fast) {
                removeLoop(slow, node);
                return 1;
            }
        }
//if no loop
        return 0;
    }
 
    // Function to remove loop
    void removeLoop(Node loop, Node head)
    {
        Node loopNode = loop;
        Node curr = loop;
 
        // Count the number of nodes in loop
        int k = 1;
        while (loopNode.next != curr) {
            loopNode = loopNode.next;
            k++;
        }
 
        // Fix one pointer to head
        loopNode = head;
 
        // set other pointer to k nodes after head
        curr = head;
        for (int i = 0; i < k; i++) {
            curr = curr.next;
        }
 
        //  Move both pointers at the same pace
        while (curr != loopNode) {
            loopNode = loopNode.next;
            curr = curr.next;
        }
 
        // Get pointer to the last node
        while (curr.next != loopNode) {
            curr = curr.next;
        }
 
        /* Set the next node of the loop ending node
         to null*/
        curr.next = null;
    }
 
    //  print the linked list
    void printL(Node node)
    {
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }
 
    // Driver program
    public static void main(String[] args)
    {
        LinkedList list = new LinkedList();
        list.head = new Node(55);
        list.head.next = new Node(45);
        list.head.next.next = new Node(54);
        list.head.next.next.next = new Node(63);
        list.head.next.next.next.next = new Node(56);
 
        //  loop for testing
        head.next.next.next.next.next = head.next.next;
        list.detectLoop(head);
        System.out.println("Linked List after removing loop : ");
        list.printL(head);
    }
}

Output Screenshot

Python Code

# Node class
class Node: 
    # Constructor 
    def __init__(self, data):
        self.data = data
        self.next = None
 
class LinkedList:
 
    # Function to initialize head
    def __init__(self):
        self.head = None
 
    def detectLoop(self):
        slow = fast = self.head
         
        while(slow and fast and fast.next):
            slow = slow.next
            fast = fast.next.next
 
            # If slow and fast meet then there is a loop
            if slow == fast:
                self.removeLoop(slow)
         
                # Return 1 if a loop is found
                return 1
         
        # Return 0 if there is no loop
        return 0
 
    # Function to remove loop
    # loop_node --> pointer to one of the loop nodes
    # head --> Pointer to the start node of the linked list
    def removeLoop(self, loop_node):
        loopnode= loop_node
        curr = loop_node
         
        # get number of nodes in loop
        k = 1
        while(loopnode.next != curr):
            loopnode = loopnode.next
            k += 1
 
        # set one pointer to head
        loopnode = self.head
         
        # other pointer to k nodes after head
        curr= self.head
        for i in range(k):
            curr = curr.next

        # Move both pointers at the same pace
        while(curr != loopnode):
            loopnode = loopnode.next
            curr = curr.next
 
        # Get pointer to the last node
        while(curr.next != loopnode):
            curr = curr.next
 
        # Set the next node of the loop ending node to null
        curr.next = None
 
    # insert a new node at the beginning
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

    # print the linked LinkedList
    def printL(self):
        temp = self.head
        while(temp):
            print (temp.data)
            temp = temp.next
 
 
# Driver program
llist = LinkedList()
llist.push(55)
llist.push(45)
llist.push(54)
llist.push(63)
llist.push(41)
 
# Create a loop for testing
llist.head.next.next.next.next.next = llist.head.next.next
 
llist.detectLoop()
 
print ("after removing loop")
llist.printL()

Output Screenshot

C++ Code

#include <bits/stdc++.h>
using namespace std;
 
/* Linked list node */
struct Node {
    int data;
    struct Node* next;
};
 
/*  remove loop. */
void removeLoop(struct Node*, struct Node*);
 
/* This function detects and removes loop in the list
  If loop is present returns 1,
  otherwise returns 0 */
int detectLoop(struct Node* list)
{
    struct Node *slow = list, *fast = list;
 
    // loop exists or not
    while (slow && fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;

        /* If slow and fast meet  then there
           is a loop */
        if (slow == fast) {
            removeLoop(slow, list);
 
            /* Return 1 if loop is found */
            return 1;
        }
    }
 
    /* Return 0 if there is no loop*/
    return 0;
}
 
/* Function to remove loop.
 loop_node : Pointer to one of the loop nodes
 head : Pointer to the start node of the linked list */
void removeLoop(struct Node* loop_node, struct Node* head)
{
    struct Node* loopnode = loop_node;
    struct Node* curr = loop_node;
 
    // Count the number of nodes in loop
    unsigned int k = 1;
    while (loopnode->next != curr) {
        loopnode = loopnode->next;
        k++;
    }
 
    // Fix one pointer to head
    loopnode = head;
 
    // And the other pointer to k nodes after head
    curr= head;
    for (int i = 0; i < k; i++)
        curr = curr->next;
 
    /*  Move both pointers at the same pace,
      they will meet at the loop’s starting node */
    while (curr != loopnode) {
        loopnode = loopnode->next;
        curr = curr->next;
    }
 
    // Get pointer to the last node
    while (curr->next != loopnode)
        curr = curr->next;
 
    /* Set the next node of the loop ending node
      to null */
    curr->next = NULL;
}
 
/*  print linked list */
void printL(struct Node* node)
{
    // Print the list after loop removal
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
}
 
struct Node* newNode(int key)
{
    struct Node* temp = new Node();
    temp->data = key;
    temp->next = NULL;
    return temp;
}
 
// Driver Code
int main()
{
    struct Node* head = newNode(55);
    head->next = newNode(45);
    head->next->next = newNode(54);
    head->next->next->next = newNode(63);
    head->next->next->next->next = newNode(56);
 
    /*loop for testing */
    head->next->next->next->next->next = head->next->next;
 
    detectLoop(head);
    cout << "List after removing loop \n";
    printL(head);
    return 0;
}

Output Screenshot

Time Complexity

The time complexity of this approach is O(n).

Space Complexity

Since we are not using any additional space, the space complexity of this approach is O(1).

Using Hashing

• We can also try using a HashSet.
• We insert each node in the hash set, before inserting, we check if it is already present in the hash set, if yes, we set the next of last node in the cycle as null.

• If not, we insert that node in the hash set.

Java Code

import java.util.*;
 
class LinkedList {
 
static Node head; // head of list
 
/* Node*/
static class Node {
     int val;
     Node next;
     Node(int d)
     {
         val = d;
         next = null;
     }
}
 
/* Inserts a new Node at front  */
static public void push(int new_data)
{
    
     Node new_node = new Node(new_data);
 
     //set the next of new node as head
     new_node.next = head;
 
     //set the value of head node as new_node
     head = new_node;
}
 
//  print the linked list
void printL(Node node)
{
     while (node != null) {
         System.out.print(node.val + " ");
         node = node.next;
     }
}
 
// Returns true if the loop is removed else returns false.
static boolean removeLoop(Node h)
{
     HashSet<Node> set = new HashSet<Node>();
     Node prev = null;
     while (h != null) {
         // If we already have this node it means there is a cycle and we
         // to remove this cycle set the next of
         // the previous node with null.
 
         if (set.contains(h)) {
             prev.next = null;
             return true;
         }
 
         // If we are seeing the node for
         // the first time, insert it in hash
         else {
             set.add(h);
             prev = h;
             h = h.next;
         }
     }
 
     return false;
}
 
/* Driver program */
public static void main(String[] args)
{
     LinkedList llist = new LinkedList();
 
     llist.push(55);
     llist.push(45);
     llist.push(54);
     llist.push(63);
 
     /*Create loop for testing */
     llist.head.next.next.next.next = llist.head;
 
     if (removeLoop(head)) {
         System.out.println("Linked List after removing loop");
         llist.printL(head);
     }
     else
         System.out.println("No Loop found");
}
}

Output Screenshot

Python Code

# List Node
class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
 
 
# nction to print list
def printList(head):
    curr = head
    while curr:
        print(curr.data, end=" —> ")
        curr = curr.next
    print("None")
 
 
# identify and remove cycle in a  list using hashing
def removeCycle(head):
    prev = None        # previous pointer
    curr = head        # main pointer
 
    # maintain a set to store visited nodes
    s = set()
 
    # traversing  the list
    while curr:
        if curr in s:
            prev.next = None
            return
 
        # insert the current node into the set
        s.add(curr)
 
        # update the previous pointer to the current node and
        # move the main pointer to the next node
        prev = curr
        curr = curr.next
 
 
if __name__ == '__main__':
    # total number of nodes in the linked list
    n = 5
 
    # construct a linked list
    head = None
    for i in reversed(range(1, n + 2)):
        head = Node(i, head)
 
    # insert cycle
    head.next.next.next.next.next = head.next
 
    removeCycle(head)
    printList(head)

Output Screenshot

C++ Code

#include <bits/stdc++.h>
using namespace std;
 
struct Node {
    int val;
    struct Node* next;
};
 
Node* newNode(int val)
{
    Node* temp = new Node;
    temp->val = val;
    temp->next = NULL;
    return temp;
}
 
//  function to print a list
void printList(Node* head)
{
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}
 
// Function to detect and remove loop
void hashAndRemove(Node* head)
{
    // hash map hashes addresses of the list nodes
    unordered_map<Node*, int> node_map;
    // pointer to last node
    Node* last = NULL;
    while (head != NULL) {
        //  insert node in the map
        if (node_map.find(head) == node_map.end()) {
            node_map[head]++;
            last = head;
            head = head->next;
        }
        // if node present in map already, there is a cycle, make the last node's next pointer      // as NULL
        else {
            last->next = NULL;
            break;
        }
    }
}
/* Driver program */
int main()
{
    Node* head = newNode(55);
    head->next = head;
    head->next = newNode(45);
    head->next->next = newNode(54);
    head->next->next->next = newNode(63);
    head->next->next->next->next = newNode(56);
 
    /* loop for testing */
    head->next->next->next->next->next = head->next->next;
 
    // printList(head);
    hashAndRemove(head);
 
    printf(" List after removing loop \n");
    printList(head);
 
    return 0;
}

Output Screenshot

Time Complexity

The time complexity of this approach is O(n), where n is the number of nodes in the Linked List. Because we traverse the List entirely once while inserting each node in the Linked List.

Space Complexity

The space Complexity of this approach is O(n) because we are using extra space by taking the help of a Hash Set to store the nodes.

Conclusion

To conclude, in this article, we discussed how to find and remove loops in Linked Lists through several approaches. We discussed a naive approach and two efficient approaches and discussed their respective time and space complexities as well. We hope that you will now be able to solve this question along with it’s variations successfully.

People are also reading:

• Minimum Edit Distance
• WAP to Count no. of alphabets, digits and spaces present in a file
• Find maximum of minimum for every window size in a given array
• WAP to Print Triangle Using * Character
• Find ancestors of a given node in a Binary Tree
• Subset Sum Problem
• Clone a Singly Linked List
• Maximum size square sub-matrices with all 1’s
• Merge Sort for Linked Lists
• Convert a Binary Tree to Doubly Linked List