# Delete nodes that have a greater value on the right side in the linked list

## Introduction

In this blog, we will discuss an important problem to Delete all nodes that have a greater value on the right side in the linked list. Such problems do come in interviews. Before solving the problem, it’s recommended that a known basic traversal in the Linked List and how to reverse a Linked List.

In this blog, we dive deep into each detail to delete nodes that have a greater value on the right side.

Let’s look at the problem statement.

We will be given a head pointer of a singly linked list of size n, implement a function to delete all the nodes which have a greater valued node on the right side.

E.g.:

As 20 has a greater value of 25 on its right and similarly, for 19, we have 25 on its right side so that these nodes will be deleted from the linked list.

So our result looks like:-

Example 1

``````Input-
List = 14->15->20->12->11->NULL
Output:
List = 20->12->11->NULL``````

Explanation:

As 14 has a greater value of 15 on its right and 15 has a greater value of 20 on its right, so this two-node was deleted.

## Brute-Force Approach

First, let’s look at the naive approach that would probably strike anybody’s mind before jumping to an optimal approach.

So, the basic approach is to traverse the linked list from left to right, and for each node, check whether there is any node having a value greater than it or not on the right side. If yes, track of the delete that node. Else move to the next node.

Now let’s look at the PseudoCode.

### PseudoCode

Algorithm

``````//Delete all nodes that have a greater value on the right side
// pass list1,list2 and value target
countPairs(list)
while list != NULL
Data1 = list_value
Temp = list_next
while Temp != NULL
Data2 = Temp_value
if Data2 > Data1
Delete list
Break loop
Temp = Temp_next
list = list_next

### CODE IN C++

``````Input:
head -> 20 -> 19 -> 25 -> 23 -> 16
Output:
head -> 25 -> 23 -> 16``````

### Complexity Analysis

Time Complexity: O(n2) where n = size of first linked list and m=size of second linked list.

This is because we iterate through two nested loops. Hence it’s O(n2).

Space complexity: O(1) at the worst case because no extra space is used.

The above algorithm works in O(n2) time which is pretty slow. This gives us the motivation to improve our algorithm.

So let’s think about an efficient approach to solve the problem.

## Approach(Efficient)

This is one of the most efficient approaches to delete all nodes that have a greater value on the right side.

Now we can formulate our approach:

1. First, we have to traverse the linked list from right to left to left, so we have to reverse the linked list and traverse through left to right.
2. Now traverse the linked list and keep the track of maximum element so far.
3. For every node, we have two possibilities either node’s value is greater than or equal to the maximum value so far or less than the maximum value so far:
1. If the node’s value is greater than or equal to the maximum value so far, then update our maximum and move to the next node.
2. If the node’s value is less than the maximum value so far, delete that node and move to the next node.
4. Reverse the linked list and return it.

Let’s look at the Code.

### CODE IN C++(Efficient)

``````#include<bits/stdc++.h>
using namespace std;

class Node{
public:
int value;    //stores data of linked list
Node *next;   //pointer for next node
Node(int data){  //constructor to construct new node
value=data;  // with given data
next=NULL;
}
};

// function to reverse the linked list;
Node *prev = NULL;
Node *Next = NULL;
while(curr != NULL){
Next = curr -> next;
curr -> next = prev;
prev = curr;
curr = Next;
}
return prev;
}
/* function to Delete all nodes that have a greater value on the right side*/
// First I have to reverse the linked list
int max_so_far = INT_MIN;
int data = rev_head -> value;
if(data >= max_so_far){
max_so_far = data;
}
else { // delete the current node
delete temp;
}
}
// reverse the result and return
}

int main(){

// print the list :
}

}``````

``````Input:
head -> 20 -> 19 -> 25 -> 23 -> 16
Output:
head -> 25 -> 23 -> 16``````

### Complexity Analysis

Time Complexity: O(n) where n = size of linked list.

Space complexity: O(1) at the worst case because no extra space is used.

Q1. What is the time complexity of reversing a linked list?

Answer) Since we traverse a linked list once so time complexity is O(n) where n is a number of nodes in the linked list.

Q2. What is the difference between Singly Linked List and Doubly Linked List?

Answer) In Singly Linked List, each node has the address of the pointer to its next node, whereas, in Doubly Linked List, each node has the address of the pointers, its next node, and its previous node.

Q3. What is the Circular Linked List?

## Key Takeaways

This article taught us how to solve the problem, delete all nodes that have a greater value on the right side We also saw how to approach the problem using a naive approach followed by efficient solutions. We discussed an iterative implementation and some basic traversal in linked lists using examples, pseudocode, and code in detail.

If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information. You can get many questions similar to the problem CodeStudio 