# DELETE NODES FROM LINKED LIST

Medium.

#### Problem Statement :

Given a linked list containing N nodes, if the `(`i+1`)`th node is greater than the ith node than delete the ith node `(0<=i<=N−1)`, this repeats till there is no smaller element in the left side of any element.

#### EXAMPLE:

``````The list 11->16->10->8->5->6->2->3->NULL should be changed to 11->10->8->5->2->NULL.
Note that 16, 6, and 3 have been deleted because there is a smaller value on the left side.``````

You are encouraged to try the problem on your own before looking at the solution.
See original problem statement here

## Approach 1`(Brute force)`:

Traverse the linked list and for each node check for all its previous nodes that have the value less than it and delete them.Take care of the pointers.

`12 15 10 11 5 6 2 3`

`15 11 6 3`

`TIME COMPLEXITY: O(n*n).`

## Approach 2:

`Reverse` the list.

Refer some best sites to learn coding and Traverse the reversed list. Keep max till now.

If next node is less than max, then delete the next node, otherwise max = next node.

Reverse the list again to retain the original order.

## SOLUTIONS:

``` #include <stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node* next;
};
struct node* newnode(int x)
{
//struct node* temp=new node();
struct node* temp;
temp= (struct node *)malloc(sizeof(struct node));
temp->data=x;
temp->next=NULL;
return temp;
}
{
while(current!=NULL)
{
nxt = current->next;

// Reverse current node's pointer
current->next = prev;

// Move pointers one position ahead.
prev = current;
current = nxt;
}
return prev;
}
{
while(curr!=NULL&&curr->next!=NULL)
{
if(curr->next->data<mx->data)
{
temp=curr->next;
curr->next=temp->next;
free(temp);
}
else
{
curr=curr->next;
mx=curr;
}
}
}
{
}
int main()
{
int t;scanf("%d",&t);
while(t--)
{
int n;scanf("%d%d",&n);
int x;scanf("%d",&x);
for(int i=1;i<n;i++)
{
int y;scanf("%d",&y);
}
{
}
printf("\n");
}

return 0;
}
```
```#include <bits/stdc++.h>
using namespace std;
struct node{
int data;
node* next;
};
node* newnode(int x)
{
node* temp=new node();
temp->data=x;
temp->next=NULL;
return temp;
}
{
while(current!=NULL)
{
nxt = current->next;

// Reverse current node's pointer
current->next = prev;

// Move pointers one position ahead.
prev = current;
current = nxt;
}
return prev;
}
{
while(curr!=NULL&&curr->next!=NULL)
{
if(curr->next->data<mx->data)
{
temp=curr->next;
curr->next=temp->next;
free(temp);
}
else
{
curr=curr->next;
mx=curr;
}
}
}
{
}

int main()
{
int t;cin>>t;
while(t--)
{
int n;
cin>>n;
int x;cin>>x;
for(int i=1;i<n;i++)
{
int y;cin>>y;
}
{
}
cout<<"\n";
}

return 0;
}
```
``` import java.util.*;
import java.io.*;
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
void delLesserNodes()
{
reverseList();
_delLesserNodes();

reverseList();
}
void _delLesserNodes()
{
Node temp;

while (current != null && current.next != null) {
if (current.next.data < maxnode.data) {
temp = current.next;
current.next = temp.next;
temp = null;
}
else {
current = current.next;
maxnode = current;
}
}
}
void push(int new_data)
{
Node new_node = new Node(new_data);
}
void reverseList()
{
Node prev = null;
Node next;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
}
void printList()
{
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int t= sc.nextInt();
while(t-- >0 ){
int n = sc.nextInt();
int p[]=new int[n];
for(int i=0;i<n;i++)
{
p[i] = sc.nextInt();
}
for(int i=n-1;i>=0;i--)
{
llist.push(p[i]);
}

llist.delLesserNodes();
llist.printList(); }
}
}
```

## One thought on “DELETE NODES FROM LINKED LIST”

1. WWW.XMC.PL says:

Stumbled into this website by chance but I’m sure glad I clicked on that link. You certainly answered all the questions I’ve been dying to answer for some time now. Will undeniably come back for more of this. Thank you so much