Examples:

INPUT: Linked list = 15 -> 14 -> 12 -> 10 and val = 14

OUTPUT: 15 -> 12 -> 10

INPUT: Linked list = 15 -> 12 -> 10 and val = 20

OUTPUT: Element not present in the list

void del(node* &head, int val)
{
    if (head == NULL) {
        cout << "Element not present in the list\n";
        return;
    }
    if (head->info == val) {
        node* t = head;
        head = head->link;
        delete (t);
        return;
    }
    del(head->link, val);
}

Intuition:

• We are passing node* (node pointer) as a reference to the 'del' function (as in node* &head).

• Suppose node containing 'val' is the first node, head = head->next changes the actual head in the main function which now points to the current beginning of the list (which was second node before deletion).

• Deleting any other node, now since current node* is derived from previous node's next and previous node's next is passed by reference , thus we can say that the pointer being on the current node can alter previous node's next.

• Thus when we do head = head->next means previous node's next gets changed to head->next which is the required operation while deletion of a node in the linked list.

• Thus there is no need to have a separate case for deletion of first node or last node.

Linked List implementation code:

//Author: @yoji_20 aka Yogesh Vaishnav
#include<bits/stdc++.h>
using namespace std;

struct node{
	int info;
	node *link = NULL;
	node(){}
	node(int a):info(a){}
};


//Deletes the node containing 'info' part as val and alter the head of the linked list

void del(node* &head, int val){
	if(head == NULL){
		cout<<"Element not present in the list\n";
		return;
	}
	if(head->info == val){
		node *t = head;
		head = head->link;   
		delete(t);
		return;
	}
	del(head->link, val);
}



//Utility function to add a node in the linked list
void push(node* &head, int data){
	node* newNode = new node(data);
	newNode->link = head;
	head = newNode;
}


//Utility function to print the linked list (recursive method)
void print(node* head){
	if(head == NULL and cout<<endl)return; //cout<<endl gets implicitly typecasted to bool value 'true'
	cout<<head->info<<' ';
	print(head->link);
}

int main(){
	
	node* head = NULL;
	push(head, 10);
	push(head, 12);
	push(head, 14);
	push(head, 15);
	print(head);
	del(head, 20);
	print(head);
	del(head,10);
	print(head);
	del(head,14);
	print(head);
	del(head, 15);
	print(head);
	
	return 0;
}

OUTPUT:

15 14 12 10

Element not present in the list

15 14 12 10

15 14 12

15 12

12