### Introduction

The linked list is one of the most important concepts to know while preparing for interviews. Having a good grasp of a linked list can be a huge plus point in coding interviews.

### Problem Statement

We will be given a circular linked list and a position, and we need to delete the element present at that position in the list.

**Note:** we need to follow 0 based indexing while deleting the nodes

### Problem Statement Understanding

Let’s try to understand the problem with the help of an example.

If the linked list given to us is:

Now, if **position = 0**.

- Then, we need to delete the first node of the list, and after deletion, the list will now look like this:

If the **position = 2**.

- Then, we need to delete the third node, and the list after deletion will look like this:

At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.

Before moving to the approach section, try to think about 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

We will divide our problem into three sections:

1) When **position = 0**:

a) It means that we need to delete the first node of the circular linked list.

b) In this case, we need to reach the last node and then connect it with the second node.

c) After that, we will update the head pointer for the list.

2) When **position = length of the list** (we need to delete the last node):

a) In this case, we need to reach the last second node and connect it with the first node.

3) When we need to delete a middle node:

a) We need to keep track of node position while iterating the list.

b) when we find the node at the specified position, we need to connect its previous node with its next node.

Let’s move to the algorithm section to see the above approach in more depth.

### Algorithm

1) First, calculate the length of the list and save it in **len** variable.

2) Initialize a variable **count** by 1.

3) If the **head** is NULL, then it means that the list is empty, so return from the function.

4) If the **position** is less than **0** or greater than **len**, then return from the function.

5) If **position == 0** then, call **deleteFirstNode function**:

- Initialize
**curr**and**left**with the head of the list. - Return from the function if the
**head**is NULL. - Make the
**head**NULL and return from the function, if**left->next**is**left**(this is the case when there is only 1 node in the list). - Run a while loop till
**left->next**is not equal to**head**.- Inside the loop, advance
**left**by one node and update**curr**with the next node of**left**.

- Inside the loop, advance
- Now, when the loop is executed completely, connect the next pointer of
**left**to the next node of**curr**. - Update the
**head**node by**left->next**. - Delete the old head node, i.e.,
**curr**.

6) If**position == (len-1)**then, call**deleteLastNode function**: - Initialize the
**curr**pointer with**head**and**left**with NULL. - Return from the function if the
**head**is NULL. - Make the
**head**NULL and return from the function, if**curr->next**is**curr**(this is the case when there is only 1 node in the list). - Run a while loop till
**curr->next**is not equal to**head**.- Inside the loop, save the value of
**curr**in**left**and advance**curr**by one node.

- Inside the loop, save the value of
- Now, when the loop is executed completely, connect the next pointer of
**left**to the next node of**curr**. - Update the
**head**node by**left->next**. - Delete the old head node, i.e.,
**curr**.

7) Run a while loop till**len**is positive. - If position is equal to
**count**then,- Connect
**previous node’s next pointer**to**current node’s next pointer**. - Delete the
**curr**pointer and return from the function.

- Connect
- Advance
**previous**by one node and update**curr**to the node next to**previous**. - Decrement
**len**and increment**count**by one.

8) Return from the function once while loop breaks.

### Dry Run

### Code Implementation

#includeusing namespace std; class Node { public: int data; Node* next; Node(int d) { data = d; next = NULL; } }; // This function will print data of // all the nodes present in the list void Display(Node* head) { Node* temp = head; // In case of an empty list: if (head == NULL) { printf("\nDisplay List is empty\n"); return; } // iterate the complete list else { do { cout<<(temp->data); temp = temp->next; cout<<" "; } while (temp != head); } cout<<'\n'; } // This function calculates the // number of nodes in the list int Length(Node* head) { Node* temp = head; int len = 0; // in case of an empty list, return 0 if (head == NULL) { return 0; } // iterate the complete list else { do { temp = temp->next; len++; } while (temp != head); } return len; } // This node deletes the first node // of the list void deleteFirstNode(Node** head) { Node *left = *head, *curr = *head; // if the list is empty if (*head == NULL) { printf("\nList is empty\n"); return; } // In case, the list has a single node if (left->next == left) { *head = NULL; return; } // iterate the complete list while (left->next != *head) { left = left->next; curr = left->next; } // left will be pointing to the last node // and curr will be the head of the list // so, we will connect left with the curr->next left->next = curr->next; // make second node as head node *head = left->next; free(curr); return; } // This function deletes the last // node of the list void deleteLastNode(Node** head) { Node *curr = *head, *left = NULL; // if the list is empty if (*head == NULL) { printf("\nList is empty\n"); return; } // In case, the list has a single node if (curr->next == curr) { *head = NULL; return; } //iterate the list while (curr->next != *head) { left = curr; curr = curr->next; } left->next = curr->next; *head = left->next; free(curr); return; } void deleteAtPosition(Node** head, int position) { // find length of the list int len = Length(*head); int count = 1; Node *previous = *head, *curr = *head; // check if the list is empty if (*head == NULL) { printf("\nDelete Last List is empty\n"); return; } // check if the given position is out of // bound of the list if (position >= len || position < 0) { printf("\nposition is not Found\n"); return; } // first node deletion if (position == 0) { deleteFirstNode(head); return; } // last node deletion else if(position == len-1){ deleteLastNode(head); return; } // iterate the complete list while (len > 0) { // delete the node when position is found if (position == count) { previous->next = curr->next; free(curr); return; } previous = previous->next; curr = previous->next; len--; count++; } return; } int main() { Node *head = new Node(3); head->next = new Node(7); head->next->next = new Node(2); head->next->next->next = new Node(5); head->next->next->next->next = head; cout<<"Original list "; Display(head); cout<<"After deleting third node "; deleteAtPosition(&head,2); Display(head); cout<<"After deleting last node "; deleteAtPosition(&head,Length(head)-1); Display(head); cout<<"After deleting first node "; deleteAtPosition(&head,0); Display(head); }

#include#include struct Node { int data; struct Node* next; }; // This function will print data of // all the nodes present in the list void Display(struct Node* head) { struct Node* temp = head; // In case of an empty list: if (head == NULL) { printf("\nDisplay List is empty\n"); return; } // iterate the complete list else { do { printf("%d",temp->data); temp = temp->next; printf(" "); } while (temp != head); } printf("\n"); } // This function calculates the // number of nodes in the list int Length(struct Node* head) { struct Node* temp = head; int len = 0; // in case of an empty list, return 0 if (head == NULL) { return 0; } // iterate the complete list else { do { temp = temp->next; len++; } while (temp != head); } return len; } // This node deletes the first node // of the list void deleteFirstNode(struct Node** head) { struct Node* left = *head; struct Node *curr = *head; // if the list is empty if (*head == NULL) { printf("\nList is empty\n"); return; } // In case, the list has a single node if (left->next == left) { *head = NULL; return; } // iterate the complete list while (left->next != *head) { left = left->next; curr = left->next; } // left will be pointing to the last node // and curr will be the head of the list // so, we will connect left with the curr->next left->next = curr->next; // make second node as head node *head = left->next; free(curr); return; } // This function deletes the last // node of the list void deleteLastNode(struct Node** head) { struct Node *curr = *head, *left = NULL; // if the list is empty if (*head == NULL) { printf("\nList is empty\n"); return; } // In case, the list has a single node if (curr->next == curr) { *head = NULL; return; } //iterate the list while (curr->next != *head) { left = curr; curr = curr->next; } left->next = curr->next; *head = left->next; free(curr); return; } void deleteAtPosition(struct Node** head, int position) { // find length of the list int len = Length(*head); int count = 1; struct Node *previous = *head, *curr = *head; // check if the list is empty if (*head == NULL) { printf("\nDelete Last List is empty\n"); return; } // check if the given position is out of // bound of the list if (position >= len || position < 0) { printf("\nposition is not Found\n"); return; } // first node deletion if (position == 0) { deleteFirstNode(head); return; } // last node deletion else if(position == len-1){ deleteLastNode(head); return; } // iterate the complete list while (len > 0) { // delete the node when position is found if (position == count) { previous->next = curr->next; free(curr); return; } previous = previous->next; curr = previous->next; len--; count++; } return; } 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; } int main() { struct Node* head = NULL; push(&head, 2); push(&head, 5); push(&head, 7); push(&head, 8); push(&head, 10); printf("Original list "); Display(head); printf("After deleting third node "); deleteAtPosition(&head,2); Display(head); printf("After deleting last node "); deleteAtPosition(&head,Length(head)-1); Display(head); printf("After deleting first node "); deleteAtPosition(&head,0); Display(head); }

class DeletetionAtPos { // structure for a node static class Node { int data; Node next; }; // Function to insert a node at the end of // a Circular linked list static Node Insert(Node head, int data) { Node current = head; // Create a new node Node newNode = new Node(); // insert data into newly created node newNode.data = data; // check list is empty // if not have any node then // make first node it if (head == null) { newNode.next = newNode; head = newNode; return head; } // if list have already some node else { // move first node to last node while (current.next != head) { current = current.next; } // put first or head node address // in new node link newNode.next = head; // put new node address into last // node link(next) current.next = newNode; } return head; } // Function print data of list static void Display( Node head) { Node current = head; // if list is empty, simply show message if (head == null) { System.out.printf("\nDisplay List is empty\n"); return; } // traverse first to last node else { do { System.out.printf("%d ", current.data); current = current.next; } while (current != head); } } // Function return number of nodes present in list static int Length(Node head) { Node current = head; int count = 0; // if list is empty // simply return length zero if (head == null) { return 0; } // traverse first to last node else { do { current = current.next; count++; } while (current != head); } return count; } // Function delete First node of // Circular Linked List static Node DeleteFirst(Node head) { Node previous = head, next = head; // check list have any node // if not then return if (head == null) { System.out.printf("\nList is empty\n"); return null; } // check list have single node // if yes then delete it and return if (previous.next == previous) { head = null; return null; } // traverse second to first while (previous.next != head) { previous = previous.next; next = previous.next; } // now previous is last node and // next is first node of list // first node(next) link address // put in last node(previous) link previous.next = next.next; // make second node as head node head = previous.next; return head; } // Function to delete last node of // Circular Linked List static Node DeleteLast(Node head) { Node current = head, previous=null; // check if list doesn't have any node // if not then return if (head == null) { System.out.printf("\nList is empty\n"); return null; } // check if list have single node // if yes then delete it and return if (current.next == current) { head = null; return null; } // move first node to last // previous while (current.next != head) { previous = current; current = current.next; } previous.next = current.next; head = previous.next; return head; } // Function delete node at a given position // of Circular Linked List static Node DeleteAtPosition( Node head, int index) { // Find length of list int len = Length(head); int count = 1; Node previous = head, next = head; // check list have any node // if not then return if (head == null) { System.out.printf("\nDelete Last List is empty\n"); return null; } // given index is in list or not if (index >= len || index < 0) { System.out.printf("\nIndex is not Found\n"); return null; } // delete first node if (index == 0) { head = DeleteFirst(head); return head; } // traverse first to last node while (len > 0) { // if index found delete that node if (index == count) { previous.next = next.next; return head; } previous = previous.next; next = previous.next; len--; count++; } return head; } // Driver Code public static void main(String args[]) { Node head = null; head = Insert(head, 99); head = Insert(head, 11); head = Insert(head, 22); head = Insert(head, 33); head = Insert(head, 44); head = Insert(head, 55); head = Insert(head, 66); // Deleting Node at position System.out.printf("Initial List: "); Display(head); System.out.printf("\nAfter Deleting node at index 4: "); head = DeleteAtPosition(head, 4); Display(head); // Deleting first Node System.out.printf("\n\nInitial List: "); Display(head); System.out.printf("\nAfter Deleting first node: "); head = DeleteFirst(head); Display(head); // Deleting last Node System.out.printf("\n\nInitial List: "); Display(head); System.out.printf("\nAfter Deleting last node: "); head = DeleteLast(head); Display(head); } }

class Node: def __init__(self, new_data): self.data = new_data self.next = None self.prev = None # This function to insert a node at the end of a list def Insert(head, data): current = head newNode = Node(0) if (newNode == None): print("\nMemory Error\n") return None newNode.data = data if (head == None) : newNode.next = newNode head = newNode return head else: while (current.next != head): current = current.next newNode.next = head current.next = newNode return head # This function will print data of all the nodes present in the list def Display(head): current = head # In case of an empty list: if (head == None): print("\nDisplay List is empty\n") return # iterate the complete list else: while(True): print( current.data,end=" ") current = current.next if (current == head): break # This function calculates the number of nodes in the list def Length(head): current = head count = 0 # in case of an empty list, return 0 if (head == None): return 0 # iterate the complete list else: while(True): current = current.next count = count + 1 if (current == head): break return count # This node deletes the first node of the list def deleteFirstNode(head): previous = head next = head if (head == None) : print("\nList is empty") return None if (previous.next == previous) : head = None return None while (previous.next != head): previous = previous.next next = previous.next previous.next = next.next head = previous.next return head # This function deletes the last node of the list def DeleteLast(head): current = head temp = head previous = None if (head == None): print("\nList is empty") return None if (current.next == current) : head = None return None while (current.next != head): previous = current current = current.next previous.next = current.next head = previous.next return head # This function delete node at a given position of List def DeleteAtPosition(head, index): # Find length of list len = Length(head) count = 1 previous = head next = head # check if the list is empty if (head == None): print("\nDelete Last List is empty") return None # check if the given position is out of bound of the list if (index >= len or index < 0) : print("\nPosition is not Found") return None # first node deletion if (index == 0) : head = deleteFirstNode(head) return head # iterate the complete list while (len > 0): # delete the node when position is found if (index == count): previous.next = next.next return head previous = previous.next next = previous.next len = len - 1 count = count + 1 return head head = None head = Insert(head, 3) head = Insert(head, 7) head = Insert(head, 2) head = Insert(head, 5) print("Original List: ") Display(head) print("\nAfter deleting node at index 3: ") head = DeleteAtPosition(head, 2) Display(head) print("\nAfter deleting last node: ") head = DeleteLast(head) Display(head) print("\nAfter Deleting first node: ") head = deleteFirstNode(head) Display(head)

#### Output

Original list 3 7 2 5

After deleting third node 3 7 5

After deleting last node 3 7

After deleting first node 7

**Time Complexity:** O(n), where n is the number of nodes in the list

[forminator_quiz id=”5474″]

So, in this blog, we have tried to explain how you can delete nodes at different positions in a circular list in the most optimal way. If you want to practice more questions on linked lists, feel free to solve them at Prepbytes (Linked Lists).