Delete nodes with higher value on right side

In the given singly linked list, remove (delete) all the nodes which have a greater value on right side.

Examples

Time complexity : O(n)

Algorithm

a. Reverse the given input linked list.

b. Traverse the reversed linked list, keep track maximum value till current node.

c. Compare current with maximum,

    1) If current < maximum, delete current.
    2) If current > maximum, update maximum and move current.

d. After reaching the end of the LL, reverse the LL to retain original order.

Algorithm working

C++ Program

#include <bits/stdc++.h>

using namespace std;

struct LLNode
{
    int data;
    struct LLNode* next;
};

//Reverse a linked list
void reverseLL(struct LLNode **head)
{
     struct LLNode *curr = *head;
     struct LLNode *prev = NULL;
     struct LLNode *next;
     while (curr != NULL)
     {
          next = curr->next;
          curr->next = prev;
          prev = curr;
          curr = next;
     }
     *head = prev;
}
//Util function to delete nodes with greater on left
void DeleteRightGreaterNodesUtil(struct LLNode *head)
{
	//Initialize maximum as head
     struct LLNode *curr = head;
     struct LLNode *maximum = head;
     struct LLNode *temp;
     while (curr != NULL && curr->next != NULL)
     {
         int current = curr->next->data;
         int max = maximum->data;
         //If current < maximum, delete current.
         if(current < max)
         {
             temp = curr->next;
             curr->next = temp->next;
             free(temp);
         }
         //If current > maximum, update maximum and move current.
         else
         {
             curr = curr->next;
             maximum = curr;
         }
     }
}
 
void DeleteRightGreaterNodes(struct LLNode **head)
{
    //Reverse LL
    reverseLL(head);
 	//Traverse the reversed LL
 	//delete nodes which have a node with gretaer value on left
    DeleteRightGreaterNodesUtil(*head);
    //Reverse again to get original order
    reverseLL(head);
}
 

/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode  **head, int dataToBeInserted)
{
    struct LLNode* curr = new LLNode;
    curr->data = dataToBeInserted;
    curr->next = NULL;    
    if(*head == NULL)
            *head=curr; //if this is first node make this as head of list
        
    else
        {
            curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
            *head=curr;
        }
        
        //O(1) constant time
}
 
//display linked list
void display(struct LLNode**node)
{
    struct LLNode *temp= *node;
    while(temp!=NULL)
        {
            if(temp->next!=NULL)
            cout<<temp->data<<"->";
            else
            cout<<temp->data;
            
            temp=temp->next; //move to next node
        }
        //O(number of nodes)
    cout<<endl;
}
/* Driver program to test above functions */
int main()
{
	//Input LL: 2->1->17->6->9->5->7->NULL
    struct LLNode *head = NULL;
    insertAtBeginning(&head,7);
    insertAtBeginning(&head,5);
    insertAtBeginning(&head,9);
    insertAtBeginning(&head,6);
    insertAtBeginning(&head,17);
    insertAtBeginning(&head,1);
    insertAtBeginning(&head,2);
 
    cout<<"Input linked list is: ";
    display(&head);
 
    DeleteRightGreaterNodes(&head);
 
    cout<<"\nOutput linked list is: ";
    display(&head);
 
     return 0;
}
Try It

 

 


Next > < Prev
Scroll to Top