Remove cycle in a Linked List

Given a pointer to the head of a singly linked list, whose last Node points to an intermediate node of the linked list, find and remove the cycle if it exists.

As you can see in the image above, Node E's next pointer points to Node C. If we remove the cycle it will point to Null which is expected by a singly linked list.

The problem can be divided into two parts:
1. Finding if the cycle exists
2. Removing the cycle

Finding the cycle:

We discussed Finding if a cycle exists in a linked list in our previous post.

We would tweak the same function to remove the cycle.

Removing the cycle:

Once the fast pointer equals the slow pointer, there are two methods to remove the cycle:

Method 1: 

1. Count number of nodes present in the loop. Let the count be k.
2. Keep slow on the head and fast on the kth node from head.
3. Move both pointers at the same pace.
4. Stop the fast node when fast.next becomes equal to slow.
5. Make fast.next = None

To count the number of nodes in the loop you could simply increment slow pointer and keep a counter to count the number of nodes until it again reaches to fast.

This approach is fairly simple to understand and I encourage you to write a code of the algorithm by making changes to the find cycle function we discussed in the earlier post.

Method 2:

1. Set slow pointer on the head.
2. Move both slow and fast both at the same pace.
3. Stop the fast node when fast.next becomes equal to slow.
4. Make fast.next = None

Proof: Why will fast.next be equal to slow at the end point of the cycle?

                                      m -> distance of the first node from the start of the cycle

                                      n  -> length of the cycle

                                      k  -> Distance of point where fast and slow meet from the start of the loop

Distance traveled by fast pointer = 2 * (Distance traveled by slow pointer)
(m + n*x + k) = 2*(m + n*y + k)

x ->  Number of complete cyclic rounds made by 
      fast pointer before they meet the first time

y ->  Number of complete cyclic rounds made by 
      slow pointer before they meet the first time

From the above equation we can say that:
m + k = (x-2y)*n

Which means m+k is a multiple of n. 

So if we move slow from the head and fast from the meeting point at the same speed they will both move 'm' nodes and as m+k is equal to 'n' hence fast.next will be equal to slow.

Code in Python:

# Python program to check if the singly linked list contains cycle or not


# Node class
class Node:

    # Constructor to initialise data and next
    def __init__(self, data=None):
        self.data = data
        self.next = None


class SinglyLinkedList:

    # Constructor to initialise head
    def __init__(self):
        self.head = None

    # Function to find cycle in linked list
    def find_cycle_remove(self):
        fast = self.head.next
        slow = self.head

        # Make fast run twice the speed of slow
        # if fast coincide with slow
        # then there is a loop or cycle
        while fast is not None:
            # break loop if cycle exists
            if fast is slow:
                break
            fast = fast.next
            if fast is not None:
                fast = fast.next
                slow = slow.next

        if fast is slow:
            slow = self.head
            while fast.next is not slow:
                fast = fast.next
                slow = slow.next
            fast.next = None
            return True

        # return False if no cycle
        return False

    # Function to Insert data at the beginning of the linked list
    def insert_at_beg(self, data):
        node = Node(data)
        node.next = self.head
        self.head = node

    # Function to print the linked list
    def print_data(self):
        current = self.head
        while current is not None:
            print(current.data, '-> ', end='')
            current = current.next
        print('None')

linked_list = SinglyLinkedList()
linked_list.insert_at_beg(9)
linked_list.insert_at_beg(8)
linked_list.insert_at_beg(7)
linked_list.insert_at_beg(6)
linked_list.insert_at_beg(5)
linked_list.insert_at_beg(4)
linked_list.insert_at_beg(3)
linked_list.insert_at_beg(2)
linked_list.insert_at_beg(1)

temp = head = linked_list.head

# get pointer to the end of the list
while temp.next is not None:
    temp = temp.next

# Make a loop in the list
temp.next = head.next.next.next

# call the find_cycle function
result = linked_list.find_cycle_remove()

# print if cycle or not
print('Yes! there was a cycle') if result else print('No! there was no cycle')
linked_list.print_data()

"""
Outputs:
Yes! there was a cycle
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> None
"""

Time Complexity:

The algorithm runs with linear time complexity as:

1. Finding cycle -> O(n)

2. Moving slow to head -> O(1)

3. Moving both fast and slow at same speed until they meet -> O(n)

Total -> O(n)

--
Have any questions or suggestions? Post in the comments below!!

By,
Anubhav Shrimal