Find cycle or loop in a Linked List

Given a pointer to the head of a singly linked list, whose last Node might point to an intermediate node of the linked list, find if the cycle exists.

Cycle in a singly linked list

As you can see in the image above, Node E's next pointer points to Node C. Hence our algorithm will return True in this case.

Finding the cycle:

Q. Why is it a hard task to find the cycle?

A. Well, if there is no cycle in the linked list you'll reach Null and hence it is not such a big deal. But, if there is a cycle then you might end up in an infinite loop as there will be no Null at the end of the linked list.

Q. So, how do we find a cycle or loop on the list?

A. Let us take an example of two runners on a circular race track. If Runner A was twice as fast as Runner B what might eventually happen? Runner A would catch up to Runner B and they would meet again because the track is circular.

Remember about the Race pointer method we discussed in Finding Middle Node in a Linked List? We could use the same approach here.

We would use two pointers, fast and slow, where fast moves twice as fast as slow. 

If there is no cycle in the linked list, fast will reach Null and we 
could safely say that there is no cycle in the list.

If while updating the pointers at a certain instance fast becomes equal to slow, 
we can say that we have found a cycle because it can only happen 
if there was a loop in the list.

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(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:
            # return True if cycle exists
            if fast is slow:
                return True
            fast = fast.next
            if fast is not None:
                fast = fast.next
                slow = slow.next

        # return False if fast is None 
        # that means there is 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


# Main Code:
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()

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

Your interviewer may still ask you a question:
Q. The fast pointer jumps twice before checking is fast is equal to slow, wouldn't it be possible that the loop will never end if fast skips slow?
A. In the linked list traversal we would have two of the following cases:

Case 1. fast is one node behind slow:

Fast pointer is one step 

behind the Slow pointer

In this case, the fast pointer will jump twice and slow would jump once and hence fast will become equal to slow.

Case 2. fast is two nodes behind slow:

Fast pointer is two nodes behind
the Slow pointer

In this case, after one iteration fast pointer will be one node behind the slow which is same as Case 1. Hence, in every case fast will reach the slow.
And that too in a single run, that is, fast would never skip the slow pointer.

Time Complexity:
O(n)
Because fast would never skip the slow pointer.

As an exercise try to think of a way to remove the cycle if it exists. I'll tell you how to remove a cycle in the next post. ;)

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

By,
Anubhav Shrimal