GeeksforGeeks - Delete nodes which have a greater value on right side

GeeksforGeeks - Delete nodes which have a greater value on right side

Given a singly linked list, remove all the nodes which have a greater value on right side.

Examples:
a) The list 12->15->10->11->5->6->2->3->NULL should be changed to 15->11->6->3->NULL. Note that 12, 10, 5 and 2 have been deleted because there is a greater value on the right side.

Method 2 (Use Reverse) 

1. Reverse the list.
2. Traverse the reversed list. Keep max till now. If next node < max, then delete the next node, otherwise max = next node.
3. Reverse the list again to retain the original order.

Time Complexity: O(n)

/* Deletes nodes which have a node with greater value node

  on left side */

void delLesserNodes(struct node **head_ref)

{

    /* 1) Reverse the linked list */

    reverseList(head_ref);

 

    /* 2) In the reversed list, delete nodes which have a node

       with greater value node on left side. Note that head

       node is never deleted because it is the leftmost node.*/

    _delLesserNodes(*head_ref);

 

    /* 3) Reverse the linked list again to retain the

       original order */

    reverseList(head_ref);

}

 

/* Deletes nodes which have greater value node(s) on left side */

void _delLesserNodes(struct node *head)

{

     struct node *current = head;

 

     /* Initialize max */

     struct node *maxnode = head;

     struct node *temp;

 

     while (current != NULL && current->next != NULL)

     {

         /* If current is smaller than max, then delete current */

         if(current->next->data < maxnode->data)

         {

             temp = current->next;

             current->next = temp->next;

             free(temp);

         }

 

         /* If current is greater than max, then update max and

            move current */

         else

         {

             current = current->next;

             maxnode = current;

         }

 

     }

}

 

/* Utility function to insert a node at the begining */

void push(struct node **head_ref, int new_data)

{

     struct node *new_node =

              (struct node *)malloc(sizeof(struct node));

     new_node->data = new_data;

     new_node->next = *head_ref;

     *head_ref = new_node;

}

 

/* Utility function to reverse a linked list */

void reverseList(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;

}

GeeksforGeeks - Delete nodes which have a greater value on right side