LinkedList is a linear data structure that is used to store the data. Unlike arrays, data is not continuously stored in the LinkedList. Each data is linked to the other using pointers. Refer to the below image for more understanding.

In this article, we find out whether the Linked list is circular. Let's start with the understanding of the circular Linked list.

In circular LinkedList, the List is not NULL terminated, and all the nodes are connected in a Circle. Refer to the below image for more understanding.

In the singly linked list, there will come a node that will point to null. But the Circular Linked List, it is not terminate the Linked list. Here it repeats the loops.

We are given a Singly LinkedList. We need to check if it is a Circular LinkedList or not.

Approach

First, we store the Head of LinkedList. Now we will start to iterate the LinkedList. If we reach the NULL or we reach the Head, we will break from there and check if we reached the head, then the LinkedList is circular else not.

There is a flaw in the above approach.

The above approach will run in an infinite loop for the following LinkedList.

To correctly check if a linked list is a circular linked list, we need to traverse the linked list using two pointers. The first pointer will move one node at a time, while the second pointer will move two nodes at a time. If the linked list is not circular, then the second pointer will reach the end of the list and will be NULL. If the linked list is circular, the second pointer will eventually meet the first pointer.

Algorithm

Initialise two pointers, slow_ptr and fast_ptr, to the head of the linked list.

Traverse the linked list using the pointers until the fast pointer reaches the end of the list (i.e., NULL), or both pointers meet.

If the fast pointer reaches the end of the list (i.e., NULL), then the linked list is not circular. Return false.

If the fast and slow pointer meets, then the linked list is circular. Return true.

Dry run

Suppose we have a linked list as below:

Initialise two pointers, slow_ptr and fast_ptr, to the head.

Slow pointer move by one and fast pointer move by 2

Next step

Next step

Next step

Next Step

In this step, both the pointer meet at 13, which results true.

C++ Implementation

#include <iostream>
// Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
bool hasCycle(ListNode *head) {
// initialize two pointers, slow_ptr and fast_ptr, to the head of the linked list
ListNode *slow_ptr = head;
ListNode *fast_ptr = head;
// traverse the linked list until the fast_ptr reaches the end (NULL) or encounters the slow_ptr
while (fast_ptr != NULL && fast_ptr->next != NULL) {
// move the slow_ptr one step at a time
slow_ptr = slow_ptr->next;
// move the fast_ptr two steps at a time
fast_ptr = fast_ptr->next->next;
// if the two pointers meet, the linked list is circular
if (slow_ptr == fast_ptr) {
return true;
}
}
// if the fast_ptr reaches the end, the linked list is not circular
return false;
}
int main() {
// create a circular linked list with five nodes
ListNode *head = new ListNode(26);
ListNode *node2 = new ListNode(34);
ListNode *node3 = new ListNode(84);
ListNode *node4 = new ListNode(69);
ListNode *node5 = new ListNode(71);
head->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = node5;
// make the linked list circular by connecting the last node to the third node
node5->next = node3;
// check if the linked list is circular
if (hasCycle(head)) {
std::cout << "The linked list is circular." << std::endl;
} else {
std::cout << "The linked list is not circular." << std::endl;
}
return 0;
}

Output

Java Implementation

// Definition for singly-linked list.
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class Solution {
public static boolean hasCycle(ListNode head) {
// initialize two pointers, slow_ptr and fast_ptr, to the head of the linked list
ListNode slow_ptr = head;
ListNode fast_ptr = head;
// traverse the linked list until the fast_ptr reaches the end (null) or encounters the slow_ptr
while (fast_ptr != null && fast_ptr.next != null) {
// move the slow_ptr one step at a time
slow_ptr = slow_ptr.next;
// move the fast_ptr two steps at a time
fast_ptr = fast_ptr.next.next;
// if the two pointers meet, the linked list is circular
if (slow_ptr == fast_ptr) {
return true;
}
}
return false; // if the fast_ptr reaches the end, the linked list is not circular
}
public static void main(String[] args) {
// create a circular linked list with five nodes
ListNode head = new ListNode(26);
ListNode node2 = new ListNode(74);
ListNode node3 = new ListNode(89);
ListNode node4 = new ListNode(43);
ListNode node5 = new ListNode(54);
head.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
// make the linked list circular by connecting the last node to the third node
node5.next = node3;
// check if the linked list is circular
if (hasCycle(head)) {
System.out.println("The linked list is circular.");
} else {
System.out.println("The linked list is not circular.");
}
}
}

Output

Complexity

Time Complexity

O(n), where n is the number of nodes in the linked list.

Reason: The above code needs to visit every node in the linked list at most twice, once by the slow_ptr and once by the fast_ptr. The time complexity is dominated by the traversal of the linked list, which takes O(n) time in the worst case.

Space Complexity

O(1)

Reason: The above code uses only two pointers, slow_ptr and fast_ptr, to traverse the linked list, and no extra data structures are created.

Frequently Asked Questions

Can we access the random element of the LinkedList?

We can not access any element of the LinkedList directly. We don’t have direct access to every element of LinkedList. If we want to access the ith element of the LinkedList, then we need to traverse the LinkedList till the ith index.

What is the purpose of a circular linked list?

A circular linked list can be used to represent data that forms a loop or cycle. For example, a circular linked list can be used to represent a round-robin scheduling algorithm, where a set of tasks are executed in a fixed order.

How do you create a circular linked list?

To create a circular linked list, you need to make the last node point back to the first node, forming a cycle. You can do this by setting the next pointer of the last node to the first node.

How do you break a circular linked list?

To break a circular linked list, you need to point the last node to NULL instead of the first node. You can do this by setting the previous node's next pointer to NULL.

What was the flaw in the first approach?

There will be a few cases in which the LinkedList will have a cycle with the Starting point being a node other than Head. In such cases, you will start your while loop from the second node. Now you will never encounter neither NULL nor the Head.

Conclusion

We have learned about circular linked lists and how to check if a linked list is circular. We have discussed the algorithm for checking if a linked list is circular, which involves using two pointers, slow_ptr and fast_ptr, that traverse the linked list.

If you want to learn more topics related to these, follow below links:

If you want to learn more about Linked List and want to practice some questions which require you to take your basic knowledge on Linked List a notch higher, then you can visit our Guided Path for Linked List.

Until then, All the best for your future endeavours, and Keep Coding.