Check if a linked list is Circular Linked List
Last Updated :
20 Feb, 2023
Given a singly linked list, find if the linked list is circular or not.
A linked list is called circular if it is not NULL-terminated and all nodes are connected in the form of a cycle. Below is an example of a circular linked list.
Note:
- An empty linked list is considered circular.
- This problem is different from cycle detection problem, here all nodes have to be part of cycle.
The idea is to store head of the linked list and traverse it. If iterator reaches NULL, linked list is not circular. else If it reaches head again, then linked list is circular.
Follow the given steps to solve the problem:
- Declare a Node pointer node and initialize it to the head’s next
- Move node pointer to the next node, while the node is not equal to nullptr and node is not equal to the head
- After coming out of the loop, check if the node is equal to head then return true, else return false
Below is the Implementation of the above approach:
C
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
int isCircular(struct Node* head)
{
if (head == NULL)
return 1;
struct Node* ptr;
ptr = head->next;
while (ptr != NULL && ptr != head)
ptr = ptr->next;
return (ptr == head);
}
struct Node* newnode(int data)
{
struct Node* temp;
temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
temp->next = NULL;
return temp;
}
int main()
{
struct Node* head = newnode(1);
head->next = newnode(2);
head->next->next = newnode(3);
head->next->next->next = newnode(4);
if (isCircular(head))
printf("Yes\n");
else
printf("No\n");
head->next->next->next->next = head;
if (isCircular(head))
printf("Yes\n");
else
printf("No\n");
return 0;
}
|
C++
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node* next;
};
bool isCircular(struct Node *head)
{
if (head == NULL)
return true;
struct Node *node = head->next;
while (node != NULL && node != head)
node = node->next;
return (node == head);
}
Node *newNode(int data)
{
struct Node *temp = new Node;
temp->data = data;
temp->next = NULL;
return temp;
}
int main()
{
struct Node* head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(3);
head->next->next->next = newNode(4);
isCircular(head)? cout << "Yes\n" :
cout << "No\n" ;
head->next->next->next->next = head;
isCircular(head)? cout << "Yes\n" :
cout << "No\n" ;
return 0;
}
|
Java
import java.util.*;
class GFG {
static class Node {
int data;
Node next;
}
static boolean isCircular(Node head)
{
if (head == null)
return true;
Node node = head.next;
while (node != null && node != head)
node = node.next;
return (node == head);
}
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
public static void main(String args[])
{
Node head = newNode(1);
head.next = newNode(2);
head.next.next = newNode(3);
head.next.next.next = newNode(4);
System.out.print(isCircular(head) ? "Yes\n"
: "No\n");
head.next.next.next.next = head;
System.out.print(isCircular(head) ? "Yes\n"
: "No\n");
}
}
|
Python3
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def Circular(head):
if head == None:
return True
node = head.next
i = 0
while((node is not None) and (node is not head)):
i = i + 1
node = node.next
return(node == head)
if __name__ == '__main__':
llist = LinkedList()
llist.head = Node(1)
second = Node(2)
third = Node(3)
fourth = Node(4)
llist.head.next = second
second.next = third
third.next = fourth
if (Circular(llist.head)):
print('Yes')
else:
print('No')
fourth.next = llist.head
if (Circular(llist.head)):
print('Yes')
else:
print('No')
|
C#
using System;
public class GFG
{
public class Node
{
public int data;
public Node next;
}
static bool isCircular( Node head)
{
if (head == null)
return true;
Node node = head.next;
while (node != null && node != head)
node = node.next;
return (node == head);
}
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
public static void Main(String []args)
{
Node head = newNode(1);
head.next = newNode(2);
head.next.next = newNode(3);
head.next.next.next = newNode(4);
Console.Write(isCircular(head)? "Yes\n" :
"No\n" );
head.next.next.next.next = head;
Console.Write(isCircular(head)? "Yes\n" :
"No\n" );
}
}
|
Javascript
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
function isCircular( head) {
if (head == null)
return true;
node = head.next;
while (node != null && node != head)
node = node.next;
return (node == head);
}
function newNode(data) {
temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
head = newNode(1);
head.next = newNode(2);
head.next.next = newNode(3);
head.next.next.next = newNode(4);
document.write(isCircular(head) ? "Yes<br/>" : "No<br/>");
head.next.next.next.next = head;
document.write(isCircular(head) ? "Yes<br/>" : "No<br/>");
|
Time Complexity: O(N)
Auxiliary Space: O(1)
Another Approach:
Below is the Implementation of the above approach:
C++
#include <iostream>
using namespace std;
class LinkedList {
private:
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
Node* head;
public:
LinkedList() {
head = nullptr;
}
void addToFront(int data) {
Node* newNode = new Node(data);
newNode->next = head;
head = newNode;
}
bool isCircular() {
if (head == nullptr) {
return false;
}
Node* slow = head;
Node* fast = head->next;
while (fast != nullptr && fast->next != nullptr) {
if (slow == fast) {
return true;
}
slow = slow->next;
fast = fast->next->next;
}
return false;
}
};
int main() {
LinkedList list;
list.addToFront(1);
list.addToFront(2);
list.addToFront(3);
list.addToFront(4);
cout << boolalpha << list.isCircular() << endl;
return 0;
}
|
Java
import java.util.NoSuchElementException;
public class LinkedList {
private static class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
private Node head;
public LinkedList() {
head = null;
}
public void addToFront(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
public boolean isCircular() {
if (head == null) {
return false;
}
Node slow = head;
Node fast = head.next;
while (fast != null && fast.next != null) {
if (slow == fast) {
return true;
}
slow = slow.next;
fast = fast.next.next;
}
return false;
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.addToFront(1);
list.addToFront(2);
list.addToFront(3);
list.addToFront(4);
System.out.println(list.isCircular());
}
}
|
Python3
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def add_to_front(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def is_circular(self):
if self.head is None:
return False
slow = self.head
fast = self.head.next
while fast is not None and fast.next is not None:
if slow == fast:
return True
slow = slow.next
fast = fast.next.next
return False
list = LinkedList()
list.add_to_front(1)
list.add_to_front(2)
list.add_to_front(3)
list.add_to_front(4)
print(list.is_circular())
|
C#
using System;
public class Node{
public int data;
public Node next;
public Node(int item){
data = item;
next = null;
}
}
public class GFG{
public static bool isCircular(Node head){
if(head == null) return false;
Node slow = head;
Node fast = head.next;
while(fast != null && fast.next != null){
if(slow == fast) return true;
slow = slow.next;
fast = fast.next.next;
}
return false;
}
public static Node addToFront(Node head, int data){
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
return head;
}
public static void Main(String []args){
Node head = null;
head = addToFront(head, 1);
head = addToFront(head, 2);
head = addToFront(head, 3);
head = addToFront(head, 4);
Console.WriteLine(isCircular(head));
}
}
|
Javascript
class Node{
constructor(data){
this.data = data;
this.next = null;
}
}
let head = null;
function addToFront(data){
let newNode = new Node(data);
newNode.next = head;
head = newNode;
}
function isCircular(){
if(head == null) return false;
let slow = head;
let fast = head.next;
while(fast != null && fast.next != null){
if(slow == fast) return true;
slow = slow.next;
fast = fast.next.next;
}
return false;
}
addToFront(1);
addToFront(2);
addToFront(3);
addToFront(4);
console.log(isCircular());
|
Time Complexity – O(n) – We traverse the linked list in the worst case once, therefore, the time complexity here is linear.
Space Complexity – O(1) – We use two Node pointers, slow and fast, so the space complexity is constant.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...