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

Ayush Tiwari
Last Updated: May 13, 2022

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++

//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 -> 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;


// 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 -> 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.

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

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think