Description: You are given reference to head pointer of a linked list. Your task is to write a function delLargerRight(Head) to remove every node from the list that has a larger node on the right side of it.

Eg:

Let the list be 14->15->9->11->4->6->2->3->NULL

It is changed to 15->11->6->3->NULL.

Note that 14, 9, 4 and 2 have been deleted because there is a greater value on the right side.

Algorithm:

2)      In the reversed list, delete nodes which have a node with greater value node on left side. ( Note that head node is never deleted because it is the leftmost node.)

3)  finally reverse the linked list again to get original order

C Implementation:

/* Linked List Node Structure */
struct node
{
int data;
struct node *next;
};

/* prototype for utility functions */

/* Deletes nodes with lesser values than nodes to the right of it */
{
/* Reverse the linked list */
/* In the reversed list, delete nodes which have a node with greater value node on left side. Note that head node is never deleted because it is the leftmost node.*/
/* finally reverse the linked list again to get original order */
}
/* Function to Delete nodes which have greater value node(s) on left side */
{
/* Initialize max */
struct node *temp;
while(current != NULL && current->next != NULL)
{
/* If current is smaller than max, then delete current */
if(current->next->data < maxnode->data)
{
temp = current->next;
current->next = temp->next;
free(temp);
}
/* If current is greater than max, then update max and move current */
else
{
current = current->next;
maxnode = current;
}
}
}

/* Function to reverse a linked list */
{
struct node *prev = NULL;
struct node *next;
while(current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}