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)
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++
|
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.
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:
- 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.
- Now traverse the linked list and keep the track of maximum element so far.
- 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:
- 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.
- If the node’s value is less than the maximum value so far, delete that node and move to the next node.
- Reverse the linked list and return it.
Let’s look at the Code.
CODE IN C++(Efficient)
#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 reverse the linked list;
Node* reverse_list(Node *head){
Node *prev = NULL;
Node *curr = head;
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*/
Node* delete_nodes(Node *head){
// First I have to reverse the linked list
Node *rev_head = reverse_list(head);
head = rev_head;
// traverse the linked list
int max_so_far = INT_MIN;
Node *prev = rev_head;
while(rev_head != NULL){
int data = rev_head -> value;
if(data >= max_so_far){
prev = rev_head;
rev_head = rev_head -> next;
max_so_far = data;
}
else { // delete the current node
Node *temp = rev_head;
prev->next = rev_head -> next;
rev_head = rev_head -> next;
delete temp;
}
}
// reverse the result and return
return reverse_list(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);
head = 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(n) where n = size of linked list.
Space complexity: O(1) at the worst case because no extra space is used.
Frequently Asked Questions
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?
Answer) In Circular Linked List, the tail of the linked list points to the head of the same 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.
Previous Article 
Comments
No comments yet
Be the first to share what you think