Delete smaller nodes in linked list in C++

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

C++Server Side ProgrammingProgramming

In this tutorial, we are going to learn how to delete all prime nodes from a doubly linked list.

Let's see the steps to solve the problem.

• Write struct with data, prev and next pointers.

• Write a function to insert the node into the doubly linked list.

• Initialize the doubly linked list with dummy data.

• Iterate over the doubly linked list. Find whether the current node data is less than given value or not.

• If the current data is less than the given value, then delete the node.

• Write a function to delete the node. Consider the following three cases while deleting the node.

  • If the node is head node, then move the head to next node.

  • If the node is middle node, then link the next node to the previous node

  • If the node is end node, then remove the previous node link.

Example

Let's see the code.

 Live Demo

#include using namespace std; struct Node {    int data;    Node *prev, *next; }; void insertNode(Node** head_ref, int new_data) {    Node* new_node = (Node*)malloc(sizeof(struct Node));    new_node->data = new_data;    new_node->prev = NULL;    new_node->next = (*head_ref);    if ((*head_ref) != NULL) {       (*head_ref)->prev = new_node;    }    (*head_ref) = new_node; } void deleteNode(Node** head_ref, Node* del) {    if (*head_ref == NULL || del == NULL) {       return;    }    if (*head_ref == del) {       *head_ref = del->next;    }    if (del->next != NULL) {       del->next->prev = del->prev;    }    if (del->prev != NULL) {       del->prev->next = del->next;    }    free(del);    return; } void deleteSmallerNodes(Node** head_ref, int K) {    Node* temp = *head_ref;    Node* next;    while (temp != NULL) {       next = temp->next;       if (temp->data < K) {          deleteNode(head_ref, temp);       }       temp = next;    } } void printLinkedList(Node* head) {    while (head != NULL) {       cout << head->data << " -> ";       head = head->next;    } } int main() {    Node* head = NULL;    insertNode(&head, 1);    insertNode(&head, 2);    insertNode(&head, 3);    insertNode(&head, 4);    insertNode(&head, 10);    insertNode(&head, 11);    insertNode(&head, 12);    int K = 10;    cout << "Linked List before deletion:" << endl;    printLinkedList(head);    deleteSmallerNodes(&head, K);    cout << "\nLinked List after deletion:" << endl;    printLinkedList(head); }

Output

If you execute the above program, then you will get the following result.

Linked List before deletion: 12 -> 11 -> 10 -> 4 -> 3 -> 2 -> 1 -> Linked List after deletion: 12 -> 11 -> 10 ->

Conclusion

If you have any queries in the tutorial, mention them in the comment section.

Published on 30-Dec-2020 06:55:25