.png)
Check if a Linked List is Circular
Problem Statement
Given the head of a linked list, determine whether the linked list is circular or not.
A linked list is said to be circular if the last node points back to the first node (head) instead of pointing to NULL.
Example
Example 1
Input:
10 → 20 → 30 → 40 → back to 10
Output:
Linked list is circular
Example 2
Input:
10 → 20 → 30 → 40 → NULL
Output:
Linked list is not circular
Definition
A linked list is circular if:
- It contains at least one node, and
- Starting from the head, if we keep moving to the next node, we eventually reach the head again.
Approach 1: Traversal Method (Checking Head Reference)
Idea
Traverse the linked list starting from the head.
If during traversal we encounter the head node again, the list is circular.
If we reach NULL, the list is not circular.
Algorithm
- If head == NULL, return false.
- Initialize a pointer current = head->next.
- Traverse the list:
- If current == head, return true.
- If current == NULL, return false.
- Move current = current->next.
- Repeat until a condition is met.
Time Complexity
- Best Case: O(1)
(Single node pointing to itself) - Worst Case: O(n)
(Traversal reaches the end or loops back after visiting all nodes)
Space Complexity
- O(1)
No extra space used.
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
int isCircular(struct Node* head) {
if (head == NULL)
return 0;
struct Node* current = head->next;
while (current != NULL && current != head) {
current = current->next;
}
return (current == head);
}
// Helper to create new node
struct Node* newNode(int data) {
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
temp->next = NULL;
return temp;
}
int main() {
struct Node* head = newNode(10);
head->next = newNode(20);
head->next->next = newNode(30);
head->next->next->next = newNode(40);
// Make it circular
head->next->next->next->next = head;
if (isCircular(head))
printf("Linked list is circular\n");
else
printf("Linked list is not circular\n");
return 0;
}C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
#include "cstdlib"
struct Node {
int data;
struct Node* next;
};
int isCircular(struct Node* head) {
if (head == NULL)
return 0;
struct Node* current = head->next;
while (current != NULL && current != head) {
current = current->next;
}
return (current == head);
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
struct Node* second = (struct Node*)malloc(sizeof(struct Node));
struct Node* third = (struct Node*)malloc(sizeof(struct Node));
struct Node* fourth = (struct Node*)malloc(sizeof(struct Node));
head->data = 10; head->next = second;
second->data = 20; second->next = third;
third->data = 30; third->next = fourth;
fourth->data = 40;
// Make circular
fourth->next = head;
if (isCircular(head))
printf("Linked list is circular\n");
else
printf("Linked list is not circular\n");
return 0;
}Java Implementation
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class CheckCircularLinkedList {
static boolean isCircular(Node head) {
if (head == null)
return false;
Node current = head.next;
while (current != null && current != head) {
current = current.next;
}
return current == head;
}
}
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
def is_circular(head):
if head is None:
return False
current = head.next
while current is not None and current is not head:
current = current.next
return current is head
JavaScript Implementation
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
function isCircular(head) {
if (head === null)
return false;
let current = head.next;
while (current !== null && current !== head) {
current = current.next;
}
return current === head;
}
Output
Linked list is circularApproach 2: Floyd’s Cycle Detection Algorithm (Fast and Slow Pointer)
Idea
Use two pointers:
- Slow pointer moves one step at a time.
- Fast pointer moves two steps at a time.
If the linked list is circular, both pointers will meet at some point.
Algorithm
- If head == NULL, return false.
- Initialize:
- slow = head
- fast = head
- Traverse the list:
- Move slow = slow->next
- Move fast = fast->next->next
- If slow == fast, the list is circular.
- If fast == NULL or fast->next == NULL, the list is not circular.
Time Complexity
- Best Case: O(1)
(Cycle detected early) - Average Case: O(n)
- Worst Case: O(n)
Space Complexity
- O(1)
Only two pointers are used.
C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
#include "cstdlib"
struct Node {
int data;
struct Node* next;
};
int isCircular(struct Node* head) {
if (head == NULL)
return 0;
struct Node* slow = head;
struct Node* fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
return 1; // loop detected
}
return 0;
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
struct Node* second = (struct Node*)malloc(sizeof(struct Node));
struct Node* third = (struct Node*)malloc(sizeof(struct Node));
struct Node* fourth = (struct Node*)malloc(sizeof(struct Node));
head->data = 10; head->next = second;
second->data = 20; second->next = third;
third->data = 30; third->next = fourth;
fourth->data = 40;
// Make circular
fourth->next = head;
if (isCircular(head))
printf("Linked list is circular\n");
else
printf("Linked list is not circular\n");
return 0;
}
Java Implementation
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class CheckCircularLinkedList {
static boolean isCircular(Node head) {
if (head == null)
return false;
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast)
return true;
}
return false;
}
}
Python Implementation
def is_circular(head):
if head is None:
return False
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
JavaScript Implementation
function isCircular(head) {
if (head === null) return false;
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast)
return true;
}
return false;
}
Output
Linked list is circularComparison of Approaches
| Approach | Time Complexity | Space Complexity | Best Use Case |
|---|---|---|---|
| Traversal Method | O(n) | O(1) | When circularity means last node points to head |
| Floyd’s Algorithm | O(n) | O(1) | Detect any cycle in linked list |
Edge Cases to Consider
- Empty linked list
- Single node pointing to itself
- Single node pointing to NULL
- Large linked list
Applications
- Detecting infinite loops
- Memory management
- Operating systems scheduling
- Data structure validation
Conclusion
Checking whether a linked list is circular is a common data structure problem. Using Floyd’s Cycle Detection Algorithm is the most efficient and widely accepted solution, offering linear time complexity and constant space usage. Understanding both traversal-based and pointer-based approaches helps in choosing the correct solution based on problem constraints.
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.jpg)
