Find and remove the loop in a Linked List | DSA Tutorials

To find a loop or cycle and remove it from a linked list, we have two approaches.

1. Using the visited flag in each node.
2. Hare and Tortoise/ Floyd’s cycle detection algorithm

Find and remove the loop in a linked list

First, we are going to see the visited flag method to remove the cycle in the linked list, and then we are going to learn about the Hare and Tortoise/Floyd’s cycle detection algorithm with a working example.

Visited the Flag Method to remove a loop in a linked list

Using this method, we set a flag to a value of true for each node that is visited for the first time. And if we visit the node again that has a flag set to true, then the list has a loop, and if not, then the list has no cycle or loop. But using this method, we need to update the whole list, which is why we don’t use this method to find a loop in the list.

Instead, we use the hare and tortoise algorithm to find the cycle in the list.

Hare and Tortoise Algorithm to detect the loop

This algorithm is also called Floyd’s cycle detection algorithm. In this algorithm, we use two reference tortoises and a hare. In the beginning, both reference hare and tortoise are set to the first node of the linked list. 

In every iteration, the hare reference visits two nodes at a time, and the tortoise reference visits a single node at a time. And if both references meet on the same node, then the list has a loop, and if not, then the list does not have any loops.

Let’s understand the algorithm with an example

Let’s say we have a linked list that has 8 nodes, as you see in Figure 1, and it has a cycle in it.

So first we set two references, hare and tortoise, and at the beginning of the iteration, we set both references to the first node of the list.

As we know, the tortoise reference visits one node at a time, and the hare reference visits two nodes at a time.

So now both the reference meets at the same node, then the list has a cycle.

def has_cycle(self):
    if self.find_cycle() is None:
        return False    else:
        return True
def find_cycle(self):
    if self.start is None or self.start.link is None:
        return None
    slowR = self.start
    fastR = self.start

    while fastR is not None and fastR.link is not None:
        slowR = slowR.link
        fastR = fastR.link.link
        if slowR == fastR:
            return slowR
    return None

def has_cycle(self):
    if self.find_cycle() is None:
        return False    else:
        return True
def find_cycle(self):
    if self.start is None or self.start.link is None:
        return None
    slowR = self.start
    fastR = self.start

    while fastR is not None and fastR.link is not None:
        slowR = slowR.link
        fastR = fastR.link.link
        if slowR == fastR:
            return slowR
    return None

To remove a loop in the linked list, first we need to find the length of the loop in the linked list, and then we need to find the length of the rest of the linked list, and then we need to subtract the length of the loop from the length of the rest of the linked list. So we get the whole length of the list, and then we place the null or None at the last node of the list.

Remove the loop in a linked list

After we can find the reference p and q. First, we need to find the length of a loop in the linked list.

Length of the loop in the linked list

To find the length of the loop in the linked list, we traverse one reference one node at a time among both references, and we count the number of nodes traversed by the reference. When the one reference value becomes equal to the second reference then we stop traversing. and the number of nodes that a reference traverses is the length of the loop in the linked list.

As you see in the figures below, we move the q reference one node at a time and count the number of nodes that the q variable traverses before the value of node q becomes equal to the node p.

So, after traversing the 5 nodes, the value of node q becomes equal to the value of node p. So, the length of the loop in the linked list is 5. Now we need to find the length of the rest of the linked list.

Length of the rest of the linked list

To find the length of the rest of the linked list first, we place a reference to the first node of the list between both of the references. As you see in Figure 4, we place the reference to the first node of the list.

Now we traverse one node at a time using both of the references in the list until both references meet at the same node and count the number of nodes traversed by either reference, as you see in the figures below.

As you see, after traversing the three nodes, both references meet at the same node. So now the number of nodes that are traversed by any reference has become the remaining length of the list. So now the length of the whole list is equal to the length of the cycle plus the length of the remaining list.
In the above example, the total length of the list is equal to 5+3=8. Now we place the Null or None value in the linked part of the 8th node, as you see in Figure 5.

So now we remove the loop from the list.

def remove_cycle(self):
    c = self.find_cycle()
    if c is None:
        return
    print("Node at which the cycle was detected is ", c.info)

    p = c
    q = c
    len_cycle = 0
    while True:
        len_cycle+=1
        q = q.link
        if p == q:
            break
    print("Length of cycle is :", len_cycle)

    len_rem_list = 0
    p = self.start
    while p != q:
        len_rem_list+=1
        p = p.link
        q = q.link

    print("Number of nodes not included in the cycle are : ", len_rem_list)
    length_list = len_cycle + len_rem_list
    print("Length of the list is : ", length_list)

    p = self.start
    for i in range(length_list-1):
        p = p.link
    p.link = None

def remove_cycle(self):
    c = self.find_cycle()
    if c is None:
        return
    print("Node at which the cycle was detected is ", c.info)

    p = c
    q = c
    len_cycle = 0
    while True:
        len_cycle+=1
        q = q.link
        if p == q:
            break
    print("Length of cycle is :", len_cycle)

    len_rem_list = 0
    p = self.start
    while p != q:
        len_rem_list+=1
        p = p.link
        q = q.link

    print("Number of nodes not included in the cycle are : ", len_rem_list)
    length_list = len_cycle + len_rem_list
    print("Length of the list is : ", length_list)

    p = self.start
    for i in range(length_list-1):
        p = p.link
    p.link = None