Delete nodes from the linked list which have a greater value on the right side

Delete nodes from the linked list which have a greater value on the right side

In this problem, we have given a singly linked list, and we need to remove all the nodes from it which have a greater value on the right side.

Examples:

• Suppose the list 13 -> 16 -> 9 -> 10 -> 4 -> 6 -> 1 -> 3 -> NULL. This list will be changed to 16 -> 10 -> 6 -> 3 -> NULL. In this, the nodes 13, 9, 4, 1 have been deleted because in linked list there is a greater value on the right side.
• The list 90 -> 80 -> 70 -> 60 -> 50 -> NULL will not be changed because there is no node which has the greater value on the right side.

Method:

We can do this by using the following steps:

• Firstly, we will reverse the given linked list.
• Then, we will traverse the reversed linked list and keep the max node. If the next node is less than the max node, we will delete the next node, otherwise max = next node.
• Finally, we will reverse the linked list again to maintain the order of the linked list given earlier.

C program to delete the nodes which have a greater value on the right side

 #include<stdio.h>
 #include<stdlib.h>
 struct node
 {
 int info;
 struct node *next;
 };
 struct node *start = NULL;
 // For inserting the elements in the linked list
 void add(int item)
 {
 struct node *t, *p;
 t = (struct node *)malloc( sizeof( struct node ));
 if(start == NULL)
 {
 start = t;
 start -> info = item;
 start -> next = NULL;
 return;
 }
 else
 {
 struct node *p = start;
 while(p -> next != NULL)
 {
 p = p -> next;
 }
 p -> next = t;
 p = p -> next;
 p -> info = item;
 p -> next = NULL;
 }
 }
 // For reversing the nodes of the linked list
 void reverse (struct node * t)
 {
     struct node * curr = t;
     struct node * next = NULL;
     struct node * pre = NULL;
     while(curr != NULL)
     {
         next=curr -> next;
         curr -> next = pre;
         pre = curr;
         curr = next;
    }
    start = pre;
 }
 void deleteLesser(struct node * temp)
 {
             reverse(temp); // For reversing the linked list
             delete(start); // For delete the nodes which have a node with greater value on left side.
             reverse(start); // For reversing the linked list again to maintain the original order of the linked list
 }
 // Function for delete the nodes which have a node with greater value on the left side.
 void delete(struct node * start)
 {
             struct node * curr = start;
             struct node * max = start;
             struct node * temp;
             while( curr != NULL && curr -> next != NULL)
             {
                         if(curr -> next -> info < max -> info) // If the curr is smaller than the max, then delete the curr
                         {
                                     temp = curr -> next;
                                     curr -> next = temp -> next;
                         }
                         else
                         {
                                     curr = curr -> next;
                                     max = curr;
                         }
             }
 }
 // To display the elements of the linked list
 void traverse(struct node * t)
 {
 if(t == NULL)
 {
             printf(" Linked list is empty\n");
                                     }
                                     while(t -> next != NULL)
                                     {
                         printf("%d -> ",t -> info);
                         t = t -> next;
                         }
                         printf("%d\n",t -> info);
 }
 // Driver Function
 int main()
 {
     add(13);
     add(16);
     add(9);
     add(10);
     add(4);
     add(6);
     add(1);
     add(3);
     printf("Given Linked List: \n");
     traverse(start);
     deleteLesser(start);
     printf("Linked List After deletion: \n");
     traverse(start);
     return 0;
 } 

Output:

Time Complexity: The time complexity of the above method is O(n).