How to remove a loop in a linked list

Loop in a linked list

A linked list is a commonly used data structure made up of nodes that are interlinked using pointers.

Note: Read more on a linked list here.

A linked list may contain a loop if a node points to another node that comes earlier in the chain. If this happens, a never-ending loop is created in the linked list.

Algorithm

The above method can be implemented by first going through the linked list and finding where the loop is and then removing that loop. We can follow the following steps to do this:

Find the loop using a map in Java/C++ or a dictionary in Python. We can go through the linked list and add the addresses of the nodes in the dictionary. Now, if at any node, the next node's address is already in the dictionary, the loop is at that node.
After we find the loop, we can simply point the next pointer of that node to null to remove the loop.

Code

class LinkedList:
  def __init__(self):
    self.root = None
  def removeLoop(self):
    visited_nodes = dict()
    curr = self.root
    visited_nodes[curr] = True
    while curr.after:
      try:
        if visited_nodes[curr.after]:
          curr.after = None
          return True
      except:
        visited_nodes[curr.after] = True
        curr = curr.after
    return False
LinkedList.detectLoop = detectLoop # add the detect loop function
my_list = LinkedList()
my_list.root = Node(3)
my_list.root.after = Node(9)
my_list.root.after.after = Node(13)
my_list.root.after.after.after = Node(12)
my_list.root.after.after.after.after = Node(8)
my_list.root.after.after.after.after.after = Node(15)
my_list.root.after.after.after.after.after.after = my_list.root.after.after
print("The list", "has" if my_list.detectLoop() else "does not have", "a loop")
print("\nCalling removeLoop() to remove the loop...")
my_list.removeLoop()
print("\nNow we check if the list still has a loop:")
print("The list", "has" if my_list.detectLoop() else "does not have", "a loop")

Explanation

Lines 6–8: We create a dictionary that stores the address of nodes we have already visited and sets the value to True.
Lines 9–17: The while loop iterates through the linked list. If a loop is found, it removes it (by pointing it to None) and returns True.
Lines 10–13: The try block checks if a node already exists in the visited_nodes and removes the loop if it finds one.
Lines 14–16: The catch block adds a node to the dictionary and updates the value of curr to move through the list.
Lines 21–34: We create a linked list my_list. The function detectLoop() is used to find if the list has a cycle. The function removeLoop() is called to remove the loop from the list.

How to remove a loop in a linked list

Loop in a linked list

Removing a loop

Algorithm

Code

Explanation