Remove Loop in a Linked List

In this class, We discuss Remove Loop in a Linked List.

The reader can take a complete competitive coding course. Click Here.

The reader should understand the logic of detecting the Loop in a linked list. Click Here.

Question:

Given a linked list.

The task is to remove Loop from a linked list.

Example:

Input: 1-2-3-4-5-6-7-point to the third node

Output: 1-2-3-4-5-6-7-None

First, do we need to detect whether the Loop exists or not?

If Loop exists, find the starting point where Loop formed.

In our example, a node three loop formed.

Loop ended at node 7

We need to find the last node and make it None.

Logic:

The above video explains the step-by-step logic.

Code:

class Solution:

    def detectloop(self, head):

        slow_p = head

        fast_p = head

        while(slow_p and fast_p and fast_p.next):

            slow_p = slow_p.next

            fast_p = fast_p.next.next

            if slow_p == fast_p:

                return slow_p

        return None

    def removeLoop(self, head):

        z=self.detectloop(head)

        if(z==None):

            pass

        else:

            ptr1 = z

            ptr2 = z

            k = 1

            while(ptr1.next != ptr2):

                ptr1 = ptr1.next

                k += 1

            ptr1 = head

            ptr2 = head

            for i in range(k):

                ptr2 = ptr2.next

            while(ptr2 != ptr1):

                ptr1 = ptr1.next

                ptr2 = ptr2.next

            while(ptr2.next != ptr1):

                ptr2 = ptr2.next

            ptr2.next = None