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