Description: You are given reference to head pointer of a linked list. Your task is to write a function delLargerRight(Head) to remove every node from the list that has a larger node on the right side of it.

 

If video does not load, Click here

Eg:

Let the list be 14->15->9->11->4->6->2->3->NULL

It is changed to 15->11->6->3->NULL.

Note that 14, 9, 4 and 2 have been deleted because there is a greater value on the right side.

Algorithm:

1)      Reverse the linked list

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.)

3)  finally reverse the linked list again to get original order

C Implementation:

 
/* Linked List Node Structure */
struct node
{
     int data;
     struct node *next;
};
 
/* prototype for utility functions */
void reverseList(structnode **headref);
void delLesserNodes(structnode *head);
 
/* Deletes nodes with lesser values than nodes to the right of it */
void delLargerRight(structnode **head_ref)
{
    /* Reverse the linked list */
    reverseList(head_ref);
    /* 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);
    /* finally reverse the linked list again to get original order */
    reverseList(head_ref);
}
/* Function to Delete nodes which have greater value node(s) on left side */
void delLesserNodes(structnode *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;
         }
     }
}
 
/* Function to reverse a linked list */
void reverseList(structnode **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;
}

 

Time Complexity:

O(n)

Go to top