Remove Loop in Linked List

Question

I was doing the Remove loop in Linked List challenge on Geeks for Geeks:

Given a linked list of N nodes such that it may contain a loop.

A loop here means that the last node of the link list is connected to the node at position X. If the link list does not have any loop, X=0.

Remove the loop from the linked list, if it is present.

I tried with this code:

class Solution:
    def removeLoop(self, q):
        slow,prev = q,None
        fast = q
        while slow and fast and fast.next:
            prev = fast
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                print(prev.data)
                prev.next = None
                return

But it doesn't work correctly in all the cases.

For example it removes the wrong link when this is the input list:

 1 → 2 → 3
     ↑   ↓
     └── 4

In that case it removes the link from 2 to 3, while it should remove the link from 4 to 2.

Here is the code to reproduce the problem:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Solution:
    def removeLoop(self, q):
        slow,prev = q,None
        fast = q
        while slow and fast and fast.next:
            prev = fast
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                print(prev.data)  # Outputs 2, but should output 4
                prev.next = None
                return

# Create list 1 -> 2 -> 3 -> 4 
one = Node(1)
two = Node(2)
three = Node(3)
four = Node(4)
one.next = two
two.next = three
three.next = four
# Add a link from last node to second node
four.next = two  # cycle

Solution().removeLoop(one)

I don't know where I went wrong?

Answer 1

Your algorithm is not correct. It detects the loop correctly -- using Floyd's cycle detection algorithm, but where slow and fast meet each other is not necessarily the spot where to remove the link.

As a side note: I would not name the given argument q... It is common to name the reference to the first node of a list head.

We can find the first node of the cycle by resetting one of the two references (like fast) to the head, and then let both references move at equal speeds until they meet again. Then you have found the first node that is part of the cycle.

As we really need the last node of the cycle (so we can set its next attribute to None) we need to break that second loop one step earlier:

    def removeLoop(self, head):
        slow = head
        fast = slow
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                # Detected the cycle, but still need to find last node:
                fast = head
                while fast.next != slow.next:
                    fast = fast.next
                    slow = slow.next
                slow.next = None
                return

However, if the cycle includes the head node, then we are already too late to exit that loop "one step earlier".

One way to solve this, is to prepend a dummy node to the list and make that the temporary head. That way it is sure that this head node is not part of the cycle, and we will not be "too late":

    def removeLoop(self, head):
        slow = Node(None)   # A dummy node
        slow.next = head    # Prepend it to the list
        head = fast = slow  # ...and start there
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                fast = head
                while fast.next != slow.next:
                    fast = fast.next
                    slow = slow.next
                slow.next = None
                return

Alternatively, you can do it without an extra node by having a prev reference following behind slow (not fast as you had in your code):

    def removeLoop(self, head):
        slow = fast = head
        while fast and fast.next:
            prev = slow  #  maintain a reference to predecessor of slow
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                # Detected the cycle, but still need to find last node:
                fast = head
                while fast != slow:
                    fast = fast.next
                    prev = slow  # ... also here
                    slow = slow.next
                prev.next = None  # and it will be the last node of the cycle
                return