Given a singly linked list, remove all the nodes which have a greater value on right side.
==> Consider similar questions, use extra data structure.
1.> Traverse list from start
2.> Keep popping from stack till stack.top() is less than cur element , than push cur element
3.> After the traversal , stack has only elements which don't have any greater value on its side
Key Point: reverse list, max till now
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.
Read full article from Delete nodes which have a greater value on right side | GeeksforGeeks
==> Consider similar questions, use extra data structure.
1.> Traverse list from start
2.> Keep popping from stack till stack.top() is less than cur element , than push cur element
3.> After the traversal , stack has only elements which don't have any greater value on its side
Key Point: reverse list, max till now
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.
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; } }}