Linked List: Delete nodes which have a greater value on right side using recursion

Problem Statement:

You are given a LL, you need to remove all the nodes that have a greater value to their right side

Example

Input:  11 -> 14 -> 9 -> 10 -> 4 -> 5 -> 1 -> 2 -> NULL
Output: 14 -> 10 -> 5 -> 2 -> NULL

Solution

In this solution we use reverse the list.

We follow below steps:

1. Reverse the list

2. Traverse the list, keep updating the Max value.

3. If next node is less than the max, then delete the next node else max = next node.

4. Reverse the list again.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <stack> 

using namespace std;

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

void insert_at_begenning ( struct Node **head_pointer, int data)
{
    // allocate memory for new node
    struct Node *temp_node = (struct Node*) malloc(sizeof(struct Node));

    // assign the data to new node
    temp_node->data = data;

    // initialize the new node to point to NULL
    temp_node->next = NULL;

    // if this is the first pointer, then this is the head pointer
    if (*head_pointer == NULL)
    {
        *head_pointer = temp_node;
    }
    else
    {
        // point the next of the present pointer to the head pointer
        temp_node->next = *head_pointer;

        //then move the reference of head pointer to the current pointer
        *head_pointer = temp_node;
    }
}

void display_list(struct Node **head_pointer)
{
    // take a reference to head pointer for navigation
    struct Node *temp = *head_pointer;

    while(temp != NULL)
    {
        if(temp->next != NULL)
            printf("%d -> ", temp->data);
        else
            printf("%d", temp->data);

        //navigate to next pointer
        temp = temp->next;
    }
    printf("\n");
}

void del_lesser_nodes(struct Node* head)
{
    struct Node* current = head;
 
    struct Node* maxnode = head;
    struct Node* temp;
 
    while (current != NULL && 
           current->next != NULL) 
    {
        if (current->next->data < maxnode->data) 
        {
            temp = current->next;
            current->next = temp->next;
            free(temp);
        }
        else
        {
            current = current->next;
            maxnode = current;
        }
    }
}


void reverse_list(struct Node** headref)
{
    struct Node* current = *headref;
    struct Node* prev = NULL;
    struct Node* next;
    while (current != NULL) 
    {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    *headref = prev;
}

void del_lesser_nodes_to_right(struct Node** head_ref)
{
    reverse_list(head_ref);
 
    del_lesser_nodes(*head_ref);
 
    reverse_list(head_ref);
}


   int main()
{
    struct Node *list_1 = NULL; 
    struct Node *result = NULL; 

    insert_at_begenning(&list_1,3);
    insert_at_begenning(&list_1,2);
    insert_at_begenning(&list_1,6);
    insert_at_begenning(&list_1,5);
    insert_at_begenning(&list_1,11);
    insert_at_begenning(&list_1,10);
    insert_at_begenning(&list_1,15);

    printf("Original List:\n");
    display_list(&list_1);

    del_lesser_nodes_to_right (&list_1);
 
    printf("\nUpdated List:\n");
    display_list(&list_1);

    return 0;
}

Output:

Original List:
15 -> 10 -> 11 -> 5 -> 6 -> 2 -> 3

Updated List:
15 -> 11 -> 6 -> 3