# Delete nodes that have a greater value on the right side ### Problem Statement

Given a singly linked list, implement a function to delete all the nodes which have a greater valued node on the right side.

### Problem Statement Understanding

Let’s understand this problem with the help of some examples. As 15 has a greater value of 20 on its right and similarly, for 14 we have 20 on its right side, so these nodes will be deleted from the linked list.
For all other nodes, we don’t have a greater valued node on its right. So, they will remain in the linked list. If our linked list = 1→2→3→4.

Here, each one of 1,2,3 has some number on the right which is greater than it. So, we remove them.
Only 4 has no greater valued node on its right side, so it will remain in the linked list. I hope these examples helped you in understanding what we need to do.

Now, can you think of an approach to solve this problem?

### Approach 1: Brute force

One straightforward thing we can do is for each node, we traverse all the nodes on the right of it and check whether there is any node having a value greater than it or not. If yes, we simply remove that node from the linked list, else we move to the next node.

We can implement our approach using two nested ‘for loops’.

### Algorithm

1) Iterate over all nodes using a loop
2) For each node
a) Check if there is a node on its right side with a larger value
b) If yes, then delete the current node else, move forward.

### Dry Run ### Code Implementation:

```

#include
using namespace std;

struct Node {
int val;
Node* next;

Node(int value){
val = value;
next = NULL;
}
};

Node* new_node = new Node(new_val);
}

while(i){
cout<val<<" ";
i = i->next;
}
cout<<"\n";
}

Node *prev = NULL;
while(curr!=NULL){
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}

while(curr != NULL){
if(curr->val < mx){
// delete curr node
Node* temp = curr;
prev->next = curr->next;
curr = curr->next;
delete temp;
} else {
mx = max(mx, curr->val);
prev = curr;
curr = curr->next;
}
}
// once again reverse it
}

int main(){

// 15 14 20 18 11

// 20 18 11
}
```
```#include
using namespace std;

struct Node {
int val;
Node* next;

Node(int value){
val = value;
next = NULL;
}
};

Node* new_node = new Node(new_val);
}

while(i){
cout<val<<" ";
i = i->next;
}
cout<<"\n";
}

int value = i->val;
bool found = false;
for(Node* j = i->next; j!=NULL; j = j->next){
if(j->val > value){
found = 1;
break;
}
}
if(found){
// delete node i
Node* temp = i->next;
i->val = i->next->val;
i->next = i->next->next;
delete temp;
}
else {
i = i->next;
}
}
}

int main(){

// 15 14 20 18 11

// 20 18 11
}
```
```class GreaterValue {

class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}

/* Deletes nodes which have a node with greater value node on left side */
void delLesserNodes()
{
/* 1.Reverse the linked list */
reverseList();

/* 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.*/
_delLesserNodes();

/* 3) Reverse the linked list again to retain
the original order */
reverseList();
}

/* Deletes nodes which have greater value node(s)on left side */
void _delLesserNodes()
{

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;
temp = null;
}

/* If current is greater than max, then update	max and move current */
else {
current = current.next;
maxnode = current;
}
}
}
void push(int new_data)
{

Node new_node = new Node(new_data);

}

void reverseList()
{
Node prev = null;
Node next;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
}
void printList()
{
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
public static void main(String args[])
{
GreaterValue llist = new GreaterValue();

llist.push(9);
llist.push(2);
llist.push(6);
llist.push(5);
llist.push(11);
llist.push(5);
llist.push(2);
llist.push(12);

llist.printList();

llist.delLesserNodes();

llist.printList();
}
}

```
```
class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def push(self, new_data):
new_node = Node(new_data)

def printList(self):
while(temp):
print (temp.data,end=" ")
temp = temp.next

def del_gr_right(self):

while i:
value = i.data
found = False
j = i.next

while j:
if j.data > value:
found = True
break
j = j.next

if found:
temp = i.next
i.data = i.next.data
i.next = i.next.next
temp = None
else:
i = i.next

llist.push(11)
llist.push(18)
llist.push(20)
llist.push(14)
llist.push(15)

llist.printList()
print()

llist.del_gr_right()

print ("\nLinked list after deletion is")
llist.printList()
```

#### Output

15 14 20 18 11
20 18 11

Time complexity: O(N*N), due to 2 nested for loops.
Space complexity: O(1), as we don’t use any extra space
Here, N is the total number of nodes in the given linked list.

Can we do some improvements?

If we could traverse from right to left, what improvements would it make?

### Approach 2: Reversing the linked list (optimized)

We can’t traverse a linked list from right to left, let’s reverse it.

In the reversed linked list, we need to do the opposite. We have to remove all the nodes having greater value on the left. Since now, we can traverse from left to right, we can keep track of the maximum value and delete the node whose values are less than the maximum value till that node.

After performing the required deletions, we can again reverse the linked list to get the result in the correct order.

### Algorithm

• Now traverse the linked list and keep track of the maximum value.
• At any node, if the node’s value is smaller than the maximum value till now, delete the node.
• Now we have a linked list in which all nodes having greater value on the left side have been deleted.

### Dry Run ### Code Implementation

```#include
#include

/* structure of a linked list node */
struct Node {
int data;
struct Node* next;
};

{

}

{

struct Node* temp;

while (current != NULL && current->next != NULL) {
if (current->next->data < maxnode->data) {
temp = current->next;
current->next = temp->next;
free(temp);
}

else {
current = current->next;
maxnode = current;
}
}
}

void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
}
{
struct Node* prev = NULL;
struct Node* next;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
}

{
}
printf("\n");
}
int main()
{

return 0;
}

```
```#include
using namespace std;

struct Node {
int val;
Node* next;

Node(int value){
val = value;
next = NULL;
}
};

Node* new_node = new Node(new_val);
}

while(i){
cout<val<<" ";
i = i->next;
}
cout<<"\n";
}

Node *prev = NULL;
while(curr!=NULL){
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}

while(curr != NULL){
if(curr->val < mx){
// delete curr node
Node* temp = curr;
prev->next = curr->next;
curr = curr->next;
delete temp;
} else {
mx = max(mx, curr->val);
prev = curr;
curr = curr->next;
}
}
// once again reverse it
}

int main(){

// 15 14 20 18 11

// 20 18 11
}
```
```class Node {

int data;
Node next;

public Node(int data){
this.data = data;
this.next = null;
}
}

class LLUtil{

public Node createLL(int[] arr){

Node newNode = null;
for(int i = 1; i < arr.length; i++){
newNode = new Node(arr[i]);
temp.next = newNode;
temp = temp.next;
}
}

//This function prints given linked list

}
System.out.println();
}

}

class GreaterValue {
public static void main (String[] args) {

int[] arr = {12,15,10,11,5,6,2,3};
LLUtil llu = new LLUtil();

}

}
}

```
```class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def push(self, new_data):
new_node = Node(new_data)

def printList(self):
while(temp):
print (temp.data,end=" ")
temp = temp.next

def reverse_it(self):
prev = None

while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next

return prev

def del_gr_right(self):

self.reverse_it()

while curr:
if curr.data < mx:
temp = curr
prev.next = curr.next
curr = curr.next
del temp
else:
mx = max(mx, curr.data)
prev = curr
curr = curr.next

self.reverse_it()

llist.push(11)
llist.push(18)
llist.push(20)
llist.push(14)
llist.push(15)

llist.printList()

llist.del_gr_right()

print()
llist.printList()
```

#### Output

15 14 20 18 11
20 18 11

Time complexity: O(N), as we are traversing the linked list (three times).
[forminator_quiz id=”3881″]

In this blog, we have seen how to delete nodes that have a greater value on the right by two different methods. Problems like these are good for strengthening your concepts in LinkedList. I would highly recommend you to practice more such problems from Linked List.

## One thought on “Delete nodes that have a greater value on the right side”

1. ‏s8 plus cases says:

Thank you ever so for you blog article.Thanks Again. Keep writing.