Check If A Linked List Is Circular Linked List

Problem Statement

Given a singly linked list, check if it is circular or not.

Examples

Input:

Output: NO

Input:

Output: YES

Input:

Output: NO

Problem Statement Understanding

Before checking for a circular linked list, do you know what is a circular linked-list?

A linked list is called circular if its last node points back to its first node.

Now we will be able to understand the examples given above.

  • For linked list

Here the last node points to NULL, hence it is not a circular linked-list.

  • For linked list

Here the last node points back to the first node, hence it is a circular linked-list.

  • For the linked list

Here, the last node points don’t point back to the first node. So, it is not a circular linked list.

I hope you got the problem, now before moving to the approach section, try to think how will you approach it?

Approach 1

One simple approach is to store the head of the linked list and now start traversing the linked list from next node of head and check if:

  • We again reached the head, it means that the linked list is circular linked list.
  • If we reached null, or we got stuck in a cycle that doesn’t include head node, it means that the linked list is not a circular linked list.

This approach is pretty simple, but here we will see how using cycle detection technique we find out if a linked list is circular or not in the next approach.

Approach 2

I hope you got an idea of what a circular linked list is.

Let’s now look at how to identify such a linked list.

Helpful Observations

  • One thing we can observe is that only the linked lists containing a cycle can be a circular linked-list. So, if a linked list doesn’t have any cycle, we know that it is not circular.
  • Another observation is that circular linked-lists have a cycle, and the cycle starts at the first node itself.
  • So, finally, a linked list with a cycle will be called a circular linked list only if the point at which the cycle starts is the first node.

To identify a linked list as a circular linked list, we need to make the following checks:

  • If the linked list contains a cycle or not.
  • If it has a cycle, then whether the node at which the cycle starts is the head node or not.

Let’s state this in another way:

  • A linked list is called circular if the next pointer of the last node of the list points back to the first node. If this pointer points to NULL or any other previous nodes (other than the first node), then the linked list won’t be called circular.

Since it is clear what we need to do, take some time and think about how to implement it.

You must know how to detect a cycle in a linked list before proceeding further.

Below is the algorithm explaining the steps we need to take to implement our idea.

Algorithm

  • Detect a cycle in the given linked list (we will use Floyd’s cycle detection algorithm).
  • If no cycle is found, then the linked list is linear. So return false.
  • Else, if the cycle is found, find the starting point of the cycle.
  • If the first node is the starting point, then the linked list is circular and return true.
  • Else return false.

Dry Run

Code Implementation:

#include <stdio.h>
#include<stdbool.h>
#include<stdlib.h>
 
struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};

void push(struct Node** head_ref, int new_c)
{
    struct Node* new_node =
            (struct Node*) malloc(sizeof(struct Node));
    new_node->data = new_c;
    new_node->prev = NULL;
    new_node->next = (*head_ref);
    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;
     *head_ref = new_node;
}

bool isCircular(struct Node *head){
 struct Node *temp=head;
 while(temp!=NULL)
 { //if temp points to head then it has completed a circle,thus a circular linked list.
    if(temp->next==head)
        return true;
    temp=temp->next;
}

return false;

}
int main(void)
{
    struct Node* head = NULL;
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
    
    if(isCircular(head))
		printf("Yes\n");
	else
		printf("No\n");
 
}


#include<bits stdc++.h="">
using namespace std;

struct Node {
    int val;
    Node* next;

    Node(int value){
        val = value;
        next = NULL;
    }
};

void push_front(Node** head, int new_val){
    Node* new_node = new Node(new_val);
    new_node->next = *head;
    *head = new_node;
}

bool isCircular(Node* head){
    // detect cycle
    Node *slow, *fast;
    slow = fast = head;

    while(fast!=NULL && fast->next!=NULL){
        slow = slow->next;
        fast = (fast->next)->next;

        if(slow==fast) break;
    }

    if(fast==NULL) return false;
    if(fast->next == NULL) return false;


    // now we have a loop
    // find its starting point
    slow = head;
    while(slow!=fast){
        slow = slow->next;
        fast = fast->next;
    }

    // check if starting point of loop
    // is the first node
    if(slow == head) return true;
    else return false;
}



int main(){
    Node* h1 = NULL;

    push_front(&h1, 5);
    push_front(&h1, 4);
    push_front(&h1, 3);
    push_front(&h1, 2);
    push_front(&h1, 1);

    // let's check if our lined list if circular or not
    if(isCircular(h1)) cout<<"YES\n";
    else cout<<"NO\n";

    // make the next pointer of last node point to first node
    Node* i = h1;
    while(i->next!=NULL){
        i = i->next;
    }

    i->next = h1;

    // now the linked list is made circular
    // 1->2->3->4->5
    //  \----------/

    // let's check if our function finds out or not
    if(isCircular(h1)) cout<<"YES\n";
    else cout<<"NO\n";

    // make the next pointer of last node point to second node
    i->next = (h1->next);

    // now the linked list isn't circular
    // but has a loop
    // 1->2->3->4->5
    //    \--------/

    // let's check if our function finds out or not
    if(isCircular(h1)) cout<<"YES\n";
    else cout<<"NO\n";
}


 
class Circular
{
    
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" );
 
}
}

# Node structure of a doubly linked list node
class Node:
	def __init__(self, data):
		self.data = data
		self.next = None
		self.prev = None

# Using this function we will be inserting a new node in the list
def insert(head_ref, data):
	
	new_node = Node(data)
	new_node.data = data
	if (head_ref == None):

		new_node.next = new_node
		new_node.prev = new_node

	else :
		
		last = head_ref.prev
		new_node.next = head_ref
		new_node.prev = last
		last.next = new_node
		head_ref.prev = new_node
	
	head_ref = new_node
	return head_ref

# Using this function we will be merging two sorted doubly linked list
# merge2SortedDLL stands for merge two sorted doubly linked list
def merge(first, second):
	
	if (first == None):
		return second

	if (second == None):
		return first

	if (first.data < second.data) :
		first.next = merge(first.next,
						second)
		first.next.prev = first
		first.prev = None
		return first
	
	else :
		second.next = merge(first,
							second.next)
		second.next.prev = second
		second.prev = None
		return second
	
# Using this function we will be merging two sorted doubly circular linked list
# merge2SortedDCLL stands for merge two sorted doubly circular linked list
def merge2SortedDCLL(head1, head2):
	
	if (head1 == None):
		return head2

	if (head2 == None):
		return head1

	if (head1.prev.data < head2.prev.data):
		last_node = head2.prev
	else:
		last_node = head1.prev

	head1.prev.next = None
	head2.prev.next = None

	finalHead = merge(head1, head2)

	finalHead.prev = last_node
	last_node.next = finalHead

	return finalHead

# Using this function we will be printing the linked list content
def printList(head):
	temp = head

	while (temp.next != head):
		print(temp.data, end = " ")
		temp = temp.next
	
	print(temp.data, end = " ")

if __name__=='__main__':
	head1 = None
	head2 = None

	head1 = insert(head1, 7)
	head1 = insert(head1, 5)
	head1 = insert(head1, 3)
	head1 = insert(head1, 1)

	print("Original linked list 1: ", end = "")
	printList(head1)
	print()

	head2 = insert(head2, 8)
	head2 = insert(head2, 6)
	head2 = insert(head2, 4)
	head2 = insert(head2, 2)

	print("Original linked list 2: ", end = "")
	printList(head2)
	print()
	newHead = merge2SortedDCLL(head1, head2)

	print("Final Sorted List: ", end = "")
	printList(newHead)

Output

NO
YES
NO

Time complexity: O(n), where n is the number of nodes in the linked list.
[forminator_quiz id="4119"]

Through this article, we learned how to check if a linked list is circular or not. Problems like these are good for strengthening your concepts in LinkedList. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Leave a Reply

Your email address will not be published. Required fields are marked *