Last Updated: 6 Jan, 2021

Circularly Linked

Easy

Asked in companies

Solve now

Problem statement

You are given the head of a linked list containing integers, You need to find out whether the given linked list is circular or not.

Note :

1. A linked list is said to be circular if it has no node having its next pointer equal to NULL and all the nodes form a circle i.e. the next pointer of last node points to the first node.
2. An empty linked will also be considered as circular.
3. All the integers in the linked list are unique.
4. In the input, the next pointer of a node with i’th integer is linked to the node with data (i+1)’th integer (If (i+1)’th node exists). If there is no such (i+1)’th integer then the next pointer of such node is set to NULL.

Input format :

The first line of input contains an integer T, denoting the number of test cases.

The first line of each test case consists of an integer N, denoting the number of links in the linked list. 

The second line of each test case consists of N space-separated integers denoting the data of the linked list and linking between nodes of the linked list as described in the notes above.

For more clarity please refer to the sample input.

Output format :

For each test case, print ‘True’ or ‘False’ depending on whether the linked list is circular or not, in a separate line.

Note :

You don't have to print anything, it has already been taken care of. Just Implement the given function.

Constraints :

1 <= T <= 10 ^ 2
1 <= D <= 10 ^ 6, here D is data stored in the node.
0 <= N <= 10 ^ 4

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Take two Node pointers and initialise them to head of the linked list.
Iterate through the linked list as follows:
- In each iteration move the slow pointer by one node and fast by two nodes(if they exist).
If at some point of time a fast pointer becomes NULL, this means the linked list has some endpoint, hence it is not circular.
If at some point in time slow and fast pointers become equals then this means the linked list contains a loop.
Now in order to determine whether the linked list is circular or not, check the point at which slow and fast pointers become equal and are also equal to the head of the linked list.
If it is equal to head then the given linked list is circular.
If it is not then the given linked list is not circular.

Eg. In the linked list given below:

Here, the head is the pointer to the node with data = 1, now initialise slow and fast with head.

In this, after the 1st iteration, slow will start point to the node with data = 2, and fast will start point to the node with data = 3.
After the 2nd iteration, slow will start point to the node with data = 3, and fast will start point to the node with data = 1.
After the 3rd iteration, slow will start point to the node with data = 4, and fast will start point to the node with data = 3.
After the 4th iteration, slow will start point to the node with data = 1, and fast will start point to the node with data = 1.
At this point, slow and fast pointers, start pointing to the same node which is the same as head, hence this linked list is circular.

Solve now