Introduction
In this blog, we will discuss an important problem 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.
Also see, Data Structures
Let’s look at the problem statement.
We will be given a head pointer of a singly linked list of size n, implementing 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.
Recommended Topic, Floyds Algorithm
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)
Answer = 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
Return Answer CODE IN C++
//Delete all nodes that have a greater value on the right side
#include<bits/stdc++.h>
using namespace std;
// Linked list node
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 Delete all nodes that have a greater value on the right side*/
void delete_nodes(Node *head){
while(head != NULL){ // traverse the linked list
int data1 = head -> value; //select a node in first linked list
Node *temp = head;
//boolean to check if there is node in right with greater value
bool flag = false;
while(temp != NULL){ // traverse on the right side
int data2 = temp -> value;
if(data2 > data1){
flag = true;
break;
}
temp=temp->next;
}
if( flag){ // it means I have to delete this node
Node *dummy = head -> next;
head -> value = head -> next -> value;
head -> next = head -> next -> next;
delete dummy;
}
else
head = head->next;
}
// return resultant linkedlist.
return head;
}
int main(){
// create first linked list with head pointer head1
Node *head = new Node(20);
head->next = new Node(19);
head->next->next = new Node(25);
head->next->next->next = new Node(23);
head->next->next->next->next = new Node(16);
delete_nodes(head);
// print the list :
while(head){
cout<<head ->value<<” ”;
head = head->next;
}
}
Input:
head -> 20 -> 19 -> 25 -> 23 -> 16
Output:
head -> 25 -> 23 -> 16Complexity 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.
8+ registered 