How to find and remove loops in a Linked List?

Posted in

How to find and remove loops in a Linked List?
vinaykhatri

Vinay Khatri
Last updated on February 21, 2024

    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:

    Leave a Comment on this Post

    0 Comments