### Introduction

One of the most crucial data structures to learn while preparing for interviews is the linked list. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit.

A Circular Linked List is a list that has all the nodes connected to form a cycle, i.e., the last node points towards the head node to complete the loop of the cycle. There is no node pointing to the NULL, indicating the absence of any end node.

In this article, we will learn about the way of deleting a node from a Circular Linked List.

### Problem Statement

We are given a circular linked list and a node, and our task is to delete the node with a given value **X** from the given Circular Linked List i.e, after operating the deletion on the Circular Linked List, the given node must not be present in the Circular Linked List.

**Note**: Linked list do not contain duplicate nodes (nodes having same values).

### Problem Statement Understanding

Letâ€™s try to understand the problem statement with the help of examples.

Letâ€™s say if the given circular linked list is:

and **X = 14**.

- So now, according to the problem statement, we need to delete the node with value
**X**from the given circular linked list. Also linked list should maintain its property of being circular after deletion of the node. - If node with value
**X**is not present in the given circular linked list, then we will have to simply print**Given node is not present in the list**and return the head node. - If node with value
**X**is present, we will delete it from the list and return the modified list. - In this example, node with value
**X = 14**is present in the list, so we delete it and return the modified list.

- Also, you must make sure that the modified list should still be a circular linked list after deletion i.e, all the nodes are still connected forming a cycle.

Taking another example, say, If the given circular linked list is:

and **X = 7**.

- So we can see that
**X = 7**is not present in the given linked list, so we will print**Given node is not present in the list**.

Now I think from the above examples, the problem is clear. So letâ€™s see how we can approach it.

Before moving to the approach section, try to think how you can approach this problem.

- If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Letâ€™s move to the approach section.

### Approach

Our approach will be simple:

- The idea is to traverse the given circular linked list and find the position of the node which we have to delete.
- To do a traversal of the given circular linked list, we will create a new Node pointer
**curr**, which will start from the head and traverse through each node in the list until it reaches the head again.- If we reach head again without finding the
**key**(the value of the node which we have to delete) then we will simply print**Given node is not present in the list**and return the original list. - While traversing, we will also keep the track of the previously visited node using a node pointer
**prev**. The use of the**prev**pointer is that when we find the node we have to delete i.e,**(curr == key)**, we can simply make prev.next point to next of the curr node**(prev.next = curr.next)**.

- If we reach head again without finding the

- Thus, breaking the bond between the
**prev**and**curr**. But one thing to notice here is that**curr.next**will still point to the next node in the list. So to break this bond we make**curr.next**point to NULL.

- In this way, we will successfully delete the node we were asked to delete in the problem.

Now let’s move to the alogorithm section.

### Algorithm

There can persist the following cases for the deletion operation:

a) The List is empty.

- If the given list is empty, i.e., the head is assigned as NULL, then we will return NULL from the function.

b) The given node is not present in the Circular Linked List.

- If we have completely traversed the list and are unable to find the given node to be deleted, we will simply print
**Given node is not present in the list**and return the head node.

c) We have found the node.

- So, in this case, we need to keep track of the node and its previous node and can perform the suitable operations from the following:
- If the list has only one node, then we will assign the head as NULL and return the head node.
- If the list has more than or equal to two nodes, we will perform the below operations:
- First, make
**curr**pointer point to the node which we want to delete and**prev**pointer point to the previous node of**curr**. - Now, we will make the
**prev**pointer point to the next of**curr**pointer and assign the next of**curr**pointer as NULL. - Then, if the
**curr**pointer is the head node, we need to update the head node with the next of the head node. - At last, we return the head representing the new Circular Linked List.

- First, make

Let’s see the dry run of the above algorithm.

### Dry Run

### Code Implementation

#include#include /* structure for a node */ struct Node { int data; struct Node* next; }; /* Function to insert a node at the beginning of a Circular linked list */ void push(struct Node** head_ref, int data) { struct Node* ptr1 = (struct Node*)malloc(sizeof(struct Node)); ptr1->data = data; ptr1->next = *head_ref; if (*head_ref != NULL) { struct Node* temp = *head_ref; while (temp->next != *head_ref) temp = temp->next; temp->next = ptr1; } else ptr1->next = ptr1; /*For the first node */ *head_ref = ptr1; } /* Function to print nodes in a given circular linked list */ void printList(struct Node* head) { struct Node* temp = head; if (head != NULL) { do { printf("%d ", temp->data); temp = temp->next; } while (temp != head); } printf("\n"); } /* Function to delete a given node from the list */ void deleteNode(struct Node* head, int key) { if (head == NULL) return; // Find the required node struct Node *curr = head, *prev; while (curr->data != key) { if (curr->next == head) { printf("\nGiven node is not found" " in the list!!!"); break; } prev = curr; curr = curr->next; } // Check if node is only node if (curr->next == head) { head = NULL; free(curr); return; } // If more than one node, check if // it is first node if (curr == head) { prev = head; while (prev->next != head) prev = prev->next; head = curr->next; prev->next = head; free(curr); } // check if node is last node else if (curr->next == head && curr == head) { prev->next = head; free(curr); } else { prev->next = curr->next; free(curr); } } /* Driver code */ int main() { /* Initialize lists as empty */ struct Node* head = NULL; /* Created linked list will be 2->5->7->8->10 */ push(&head, 2); push(&head, 5); push(&head, 7); push(&head, 8); push(&head, 10); printf("List Before Deletion: "); printList(head); deleteNode(head, 7); printf("List After Deletion: "); printList(head); return 0; }

#include <bits/stdc++.h> using namespace std; /* structure for a node */ class Node { public: int data; Node* next; }; /* Function to insert a node at the beginning of a Circular linked list */ void push(Node** head_ref, int data) { // Create a new node and make head as next // of it. Node* ptr1 = new Node(); ptr1->data = data; ptr1->next = *head_ref; /* If linked list is not NULL then set the next of last node */ if (*head_ref != NULL) { // Find the node before head and update // next of it. Node* temp = *head_ref; while (temp->next != *head_ref) temp = temp->next; temp->next = ptr1; } else ptr1->next = ptr1; /*For the first node */ *head_ref = ptr1; } /* Function to print nodes in a given circular linked list */ void printList(Node* head) { Node* temp = head; if (head != NULL) { do { cout << temp->data << " "; temp = temp->next; } while (temp != head); } cout << endl; } /* Function to delete a given node from the list */ void deleteNode(Node** head, int key) { // If linked list is empty if (*head == NULL) return; // If the list contains only a single node if((*head)->data==key && (*head)->next==*head) { free(*head); *head=NULL; return; } Node *last=*head,*d; // If head is to be deleted if((*head)->data==key) { // Find the last node of the list while(last->next!=*head) last=last->next; // Point last node to the next of head i.e. // the second node of the list last->next=(*head)->next; free(*head); *head=last->next; return; } // Either the node to be deleted is not found // or the end of list is not reached while(last->next!=*head&&last->next->data!=key) { last=last->next; } // If node to be deleted was found if(last->next->data==key) { d=last->next; last->next=d->next; free(d); } else cout<<"no such keyfound"; } /* Driver code */ int main() { /* Initialize lists as empty */ Node* head = NULL; /* Created linked list will be 2->5->7->8->10 */ push(&head, 2); push(&head, 5); push(&head, 7); push(&head, 8); push(&head, 10); cout << "List Before Deletion: "; printList(head); deleteNode(&head, 7); cout << "List After Deletion: "; printList(head); return 0; }

class Node: def __init__(self, next = None, data = None): self.next = next self.data = data # This function is used to insert a new node at the beginning of the circular linked list. def push(head_ref, data): ptr1 = Node() ptr1.data = data ptr1.next = head_ref if (head_ref != None) : temp = head_ref while (temp.next != head_ref): temp = temp.next temp.next = ptr1 else: ptr1.next = ptr1 head_ref = ptr1 return head_ref # This is the main function which will delete the node which have value equal to key def deleteNode( head, key) : if (head == None): return if((head).data == key and (head).next == head): head = None last = head d = None if((head).data == key) : while(last.next != head): last = last.next last.next = (head).next head = last.next while(last.next != head and last.next.data != key) : last = last.next if(last.next.data == key) : d = last.next last.next = d.next else: print("no such keyfound") return head # Once we have successfully deleted the specified node, this function will be used to print the modified list. def printList( head): temp = head if (head != None) : while(True) : print( temp.data, end = " ") temp = temp.next if (temp == head): break print() head = None head = push(head, 5) head = push(head, 8) head = push(head, 3) head = push(head, 4) head = push(head, 7) head = push(head, 6) head = push(head, 9) print("List Before Deletion: ") printList(head) head = deleteNode(head, 7) print( "List After Deletion: ") printList(head)

#### Output

List Before Deletion: 9 6 7 4 3 8 5

List After Deletion: 9 6 4 3 8 5

**Time Complexity:** O(n), where n is the number of nodes in the circular linked list. Traversing the list takes a linear amount of time. Hence, the time complexity is O(n).

[forminator_quiz id=”5132″]

So, in this blog, we have tried to explain how you can delete a node from a Circular Linked List. This is a basic problem and is good for strengthening your concepts in LinkedList and if you want to practice more such problems, you can checkout Prepbytes (Linked List).