Detecting a cycle in a singly linked list.
Many a times I come across this question while going through websites who cater interview questions for Microsoft, Google, Amazon etc.
Most of the time people are not clear with the question itself. Here is an effort to describe the problem first and then check the possible solutions.
Singly Linked List: It is a data structure consisting of nodes, where each node can hold a minimum of two attributes, they are, a data value and a pointer to the next node. The singly linked list will have a head and the user is given the reference of the head to do further processing. We know nothing about any property of the given linked list (like length, values, indices for some elements etc) except for a reference to its head.
This puts us in a situation where we are compelled to traverse through the linked list to access any data in a sequential manner.
The next property of the last node of the linked list points to null. Hence, to verify if the node is the last node in the linked list, we can check if the next points to null.
We can assume a linked list to be a structure like a train, if it makes understanding easy.
Understanding the problem of cycles in a linked list
A cycle can either start or end a singly linked list. No cycle can occur in the middle. There can be only one cycle in a singly linked list.
To explain it further, we can see the below three conditions.
1) A B C D E F G H I J
above is a singly linked list of 10 nodes, it has no cycles.
2) A B C D E F G H I A
above is a singly linked list with 10 nodes and it has a cycle which starts and ends at the node A
3) A B C D E F G H I E
above is a singly linked list with 10 modes where the cycle starts at node E
Apart from the above three cases I cannot think of any other way a singly linked list can exist.
If the problem is still unclear then try reading the above section once again.
How to solve/write a code/analyze the problem?
There can be various ways of doing it, following is one of them:
Using a separate storage to keep a track of the nodes visited, needs more space with the growing size of linked list.
Explanation: In this case, start traversing the linked list with the reference to head, name the pointer as ptrFirst, store the id of the visited node in a HashSet, after every next move check the id in the HashSet. If the id exists that means the current node has been visited prior to this encounter and it proves that there exists a cycle.
Problems which arise after this is to find the length of the cycle.
More on this in the next blog...
