Circularly Linked

Easy
0/40
Average time to solve is 15m
profile
Contributed by
127 upvotes
Asked in companies
MicrosoftSAP LabsHCL Technologies

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
1
5
1 2 3 4 1
Sample Output 1 :
True
Explanation of sample input 1 :
Given Linked list look like following:

alt-text

As given linked list form a circle, hence it is a Circular linked list.
Sample Input 2 :
1
7
1 2 3 4 5 6 7
Sample Output 2 :
False
Explanation of sample input 2 :
Given Linked list look like following:

alt-text

In the given linked list there is a node at which this linked list terminates, hence it is not a circular linked list.
Hint

Use slow and fast pointers to detect a loop in the linked list.

Approaches (1)
Optimal Solution
  • 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.
Time Complexity

O(N), where N is the length of the linked list.

 

As in cases where the linked list is a straight-chain, in that case, the fast pointer reaches the end of the linked list in N/2 steps. And if a linked list contains a loop, then in that case slow and fast pointers will become equal after some iterations.

At the meeting node of slow and fast pointers, the steps taken by both pointers should be the same. Let’s say they meet after K steps, then the required steps taken by both pointers will also be K. K may take values up to N. Hence this will take O(N) order of time.

Space Complexity

O(1).

 

As we are using constant extra memory.

Code Solution
(100% EXP penalty)
Circularly Linked
Full screen
Console