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
// C program to check if the linked list is circular #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* next; }; int isCircular(struct Node* head) { // If linked list is empty it is circular if (head == NULL) return 1; struct Node* ptr; ptr = head->next; // Traversing linked list till last node while (ptr != NULL && ptr != head) ptr = ptr->next; // Condition for circular linked list return (ptr == head); } // Function to create new Node struct Node* newnode(int data) { struct Node* temp; temp = (struct Node*)malloc(sizeof(struct Node)); temp->data = data; temp->next = NULL; return temp; } // Driver's code int main() { // code // Starting with empty list struct Node* head = newnode(1); head->next = newnode(2); head->next->next = newnode(3); head->next->next->next = newnode(4); // Checking for circular list if (isCircular(head)) printf("Yes\n"); else printf("No\n"); // If not circular making it circular head->next->next->next->next = head; if (isCircular(head)) printf("Yes\n"); else printf("No\n"); return 0; } |
C++
// C++ program to check if linked list is circular #include<bits/stdc++.h> using namespace std; /* Link list Node */struct Node { int data; struct Node* next; }; /* This function returns true if given linked list is circular, else false. */bool isCircular(struct Node *head) { // An empty linked list is circular if (head == NULL) return true; // Next of head struct Node *node = head->next; // This loop would stop in both cases (1) If // Circular (2) Not circular while (node != NULL && node != head) node = node->next; // If loop stopped because of circular // condition return (node == head); } // Utility function to create a new node. Node *newNode(int data) { struct Node *temp = new Node; temp->data = data; temp->next = NULL; return temp; } // Driver's code int main() { /* Start with the empty list */ 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" ; // Making linked list circular head->next->next->next->next = head; isCircular(head)? cout << "Yes\n" : cout << "No\n" ; return 0; } |
Java
// Java program to check if // linked list is circular import java.util.*; class GFG { /* Link list Node */ static class Node { int data; Node next; } /*This function returns true if given linked list is circular, else false. */ static boolean isCircular(Node head) { // An empty linked list is circular if (head == null) return true; // Next of head Node node = head.next; // This loop would stop in both cases (1) If // Circular (2) Not circular while (node != null && node != head) node = node.next; // If loop stopped because of circular // condition return (node == head); } // Utility function to create a new node. static Node newNode(int data) { Node temp = new Node(); temp.data = data; temp.next = null; return temp; } /* Driver code*/ public static void main(String args[]) { /* Start with the empty list */ 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"); // Making linked list circular head.next.next.next.next = head; System.out.print(isCircular(head) ? "Yes\n" : "No\n"); } } // This code contributed by Arnab Kundu |
Python3
# Python3 program to check if a linked list is circular # Node class class Node: # Function to initialise the node object def __init__(self, data): self.data = data # Assign data self.next = None # Initialize next as null # Linked List class contains a Node object class LinkedList: # Function to initialize head def __init__(self): self.head = None def Circular(head): if head == None: return True # Next of head node = head.next i = 0 # This loop would stop in both cases (1) If # Circular (2) Not circular while((node is not None) and (node is not head)): i = i + 1 node = node.next return(node == head) # Driver's code 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') # This code is contributed by Sanket Badhe |
C#
// C# program to check if // linked list is circular using System; public class GFG { /* Link list Node */public class Node { public int data; public Node next; } /*This function returns true if given linked list is circular, else false. */static bool isCircular( Node head) { // An empty linked list is circular if (head == null) return true; // Next of head Node node = head.next; // This loop would stop in both cases (1) If // Circular (2) Not circular while (node != null && node != head) node = node.next; // If loop stopped because of circular // condition return (node == head); } // Utility function to create a new node. static Node newNode(int data) { Node temp = new Node(); temp.data = data; temp.next = null; return temp; } // Driver's code public static void Main(String []args) { /* Start with the empty list */ 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" ); // Making linked list circular head.next.next.next.next = head; Console.Write(isCircular(head)? "Yes\n" : "No\n" ); } } // This code has been contributed by 29AjayKumar |
Javascript
// javascript program to check if // linked list is circular /* Link list Node */class Node { constructor(val) { this.data = val; this.next = null; } } /* * This function returns true if given linked list is circular, else false. */ function isCircular( head) { // An empty linked list is circular if (head == null) return true; // Next of head node = head.next; // This loop would stop in both cases (1) If // Circular (2) Not circular while (node != null && node != head) node = node.next; // If loop stopped because of circular // condition return (node == head); } // Utility function to create a new node. function newNode(data) { temp = new Node(); temp.data = data; temp.next = null; return temp; } /* Driver code */ /* Start with the empty list */ 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/>"); // Making linked list circular head.next.next.next.next = head; document.write(isCircular(head) ? "Yes<br/>" : "No<br/>"); // This code contributed by gauravrajput1 |
Output
No Yes
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()); // Output: false } } |
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()) # Output: False |
C#
// C# code for above approach 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)); } } // THIS CODE IS CONTRIBUTED BY KIRTI AGARWAL(KIRTIAGARWAL23121999) |
Javascript
// JavaScript Program for the above approach // structure of linked list node 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; } // driver function addToFront(1); addToFront(2); addToFront(3); addToFront(4); console.log(isCircular()); // THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002) |
Output
false
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.
This article is contributed by Shivam Gupta. If you like neveropen and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
