Linked list are the favorite interview topic of many. A linked list is a data structure which contains the reference of the next node and data for the current node and it is not stored at adjacent memory location.
In this article I will discuss a simple programming problem. In the problem we have to find if the linked list provided is circular or not.
Circular Linked List
A linked list is circular if the next node of the current node points to already traversed node. Lets see it with the help of figure provided below.
As we can see in the above figure we have a linked list with six nodes. Suppose the head of the linked list is 13.
If you begin traversing the linked list starting with 13, you will soon come back to 13 node again. This confirms that linked list is circular.
But how can you determine by writing a program to achieve the same. There can be a simple way too achieve the same by having a hashset and while traversing you can keep the traversed nodes in the hashset.
Finally if the traversed node is already present in the hashset, you can come to the conclusion that the linked list is circular. But there is catch with this technique. The space complexity of this algorithm will be O(n). As we need a hashset with the same size as of linked list for worst case scenario.
The alternative can be, to store the reference or pointer of the first node and traverse the linked list and keep comparing the traversed node with the first node. And if the traversed node and the pointer have same reference, the linked list is circular. This solution looks good as we don’t have to store big amount of data.
But what if the linked list looks like as shown in the figure below.
As you can see in the above figure, the linked list is not the circular at the head. In the above case even if we keep the head of the list as the pointer to compare with, the other pointer will keep traversing the linked list in an infinite loop.
The workaround for the above problem can be to keep moving both pointers, at different speed.
C# Code Example
Lets understand it with the help of an C# code example. Below is the code for Node class.
class SinglyLinkedListNode
{
public int data;
public SinglyLinkedListNode next;
public SinglyLinkedListNode(int nodeData)
{
this.data = nodeData;
this.next = null;
}
}And below is the code to check if the linked list is circular linked list.
private static bool DeterminIfDoublyLinkedList(SinglyLinkedListNode head)
{
SinglyLinkedListNode sp;
SinglyLinkedListNode fp;
if (head == null || head.next.next == null)
return false;
sp = head;
fp = head.next.next;
while (true)
{
if (sp == fp)
return true;
else
{
if (fp.next == null || fp.next.next == null)
return false;
sp = sp.next;
fp = fp.next.next;
}
}
}Let’s walk through the above code.
As already mentioned I have taken two pointers or reference points name as sp for slow pointer and fp for fast pointer.
And I am traversing all the nodes in a loop. In the loop I am checking if anytime the fp and sp are same, it means the linked list is circular and I return a true.
And I return false if fast pointer’s next or next to next node is null, denoting that we have reached the end of the node.
You can test the above algorithm with the help of below code.
var nodes = ValuesToLinkedListNodes(new int[] { 12, 13, 15, 17, 19, 20 });
nodes[5].next = nodes[2];
Console.WriteLine(DeterminIfDoublyLinkedList(nodes[0]));I have created a circular linked list by pointing the next node of 20 to 15 as shown in the figure above.
The above code also takes care of the edge cases. Suppose there is only one element and it points to itself. Thus it creates a circular linked list with one element.
Conclusion:
It can become bit tricky to determine how to find the circular linked list if we are not aware about this logic. Moreover interviewer can still take you for a ride by asking a very good question in addition to this. His next question can be, how to determine the starting point of the circular list. I will discuss in my next article, how to find the starting point of the circular linked list.