Linked List: Deletion from a Circular Linked List

Problem Statement:

You are given a circular linked list, and a node value.
You need to delete that node from the list.

Example

Input:

-> 1 -> 2 -> 3 -> 4
   ^              |
   | _  _  _  _  _|

Node Data = 2

Output:
-> 1 - -> 3 -> 4
   ^           |
   | _  _  _  _|

Solution

The solution is very simple.

We take 2 pointers “curr” and “prev” and initialize “curr” with head.

Now we traverse the list and then check if the node to be deleted and move the curr to next, make prv to point to curr.

If the node to be deleted is the internal node, then set prev -> next = temp -> next and delete curr

If curr is the last node, then prev -> next = head and delete curr node.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <stack> 

using namespace std;

class Node 
{
public:
    int data;
    Node* next;
};
 

void push(Node** head_ref, int data)
{

    Node* ptr1 = new Node();
    ptr1->data = data;
    ptr1->next = *head_ref;
 

    if (*head_ref != NULL) 
    {

        Node* temp = *head_ref;
        while (temp->next != *head_ref)
            temp = temp->next;
        temp->next = ptr1;
    }
    else
        ptr1->next = ptr1; 
 
    *head_ref = ptr1;
}
 

void print_list(Node* head)
{
    Node* temp = head;
    if (head != NULL) {
        do {
            cout << temp->data << " ";
            temp = temp->next;
        } while (temp != head);
    }
 
    cout << endl;
}
 
void delete_node(Node** head, int key) 
{
     
    if (*head == NULL)
        return;
         
    if((*head)->data==key && (*head)->next==*head)
    {
        free(*head);
        *head=NULL;
        return;
    }
     
    Node *last=*head,*d;
     
    if((*head)->data==key) 
    {
         
        while(last->next!=*head)
            last=last->next;
             
        last->next=(*head)->next;
        free(*head);
        *head=last->next;
    }
     

    while(last->next!=*head&&last->next->data!=key) 
    {
        last=last->next;
    }
     
    if(last->next->data==key) 
    {
        d=last->next;
        last->next=d->next;
        free(d);
    }
    else
        cout<<"no such keyfound";
    }
 
int main()
{
    Node* head = NULL;
 
    push(&head, 1);
    push(&head, 2);
    push(&head, 3);
    push(&head, 4);
    push(&head, 5);
 
    cout << "List Before Deletion: ";
    print_list(head);
 
    delete_node(&head, 2);
 
    cout << "List After Deletion: ";
    print_list(head);
 
    return 0;
}

Output:

List Before Deletion: 5 4 3 2 1
List After Deletion: 5 4 3 1