# Delete nodes with higher value on right side

## In the given singly linked list, remove (delete) all the nodes which have a greater value on right side.

### Examples

Time complexity : O(n)

## Algorithm

a. Reverse the given input linked list.

b. Traverse the reversed linked list, keep track maximum value till current node.

c. Compare current with maximum,

1) If current < maximum, delete current.
2) If current > maximum, update maximum and move current.

d. After reaching the end of the LL, reverse the LL to retain original order.

## C++ Program

``````#include <bits/stdc++.h>

using namespace std;

struct LLNode
{
int data;
struct LLNode* next;
};

{
struct LLNode *prev = NULL;
struct LLNode *next;
while (curr != NULL)
{
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
}
//Util function to delete nodes with greater on left
{
struct LLNode *temp;
while (curr != NULL && curr->next != NULL)
{
int current = curr->next->data;
int max = maximum->data;
//If current < maximum, delete current.
if(current < max)
{
temp = curr->next;
curr->next = temp->next;
free(temp);
}
//If current > maximum, update maximum and move current.
else
{
curr = curr->next;
maximum = curr;
}
}
}

{
//Reverse LL
//Traverse the reversed LL
//delete nodes which have a node with gretaer value on left
//Reverse again to get original order
}

/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode  **head, int dataToBeInserted)
{
struct LLNode* curr = new LLNode;
curr->data = dataToBeInserted;
curr->next = NULL;
*head=curr; //if this is first node make this as head of list

else
{
curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
}

//O(1) constant time
}

void display(struct LLNode**node)
{
struct LLNode *temp= *node;
while(temp!=NULL)
{
if(temp->next!=NULL)
cout<<temp->data<<"->";
else
cout<<temp->data;

temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}
/* Driver program to test above functions */
int main()
{
//Input LL: 2->1->17->6->9->5->7->NULL