Last Updated on November 21, 2022 by Prepbytes
In the Below article, we are trying to delete smaller nodes in linked list and delete larger nodes in linked list. We have seen so many concepts in data structures and now at this stage we got so familiar with the major concepts such as deletion in linked list, reversing a linked list etc.
How to Delete Smaller Nodes in Linked List and Delete Larger Nodes in Linked List.
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
Explanation of how to delete smaller nodes in linked list and delete larger nodes in linked list.
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;
}
struct node* reverse(struct node* head)
{
struct node* prev=NULL,*nxt=NULL,*current=head;
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;
}
struct node* find_less(struct node* head)
{
struct node* curr=head;
struct node* mx=head,*temp;
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;
}
}
return head;
}
struct node* sort(struct node* head)
{
head=reverse(head);
head=find_less(head);
head=reverse(head);
return head;
}
int main()
{
int t;scanf("%d",&t);
while(t--)
{
int n;scanf("%d%d",&n);
int x;scanf("%d",&x);
struct node* head=newnode(x);
struct node* headlist=head;
for(int i=1;i<n;i++)
{
int y;scanf("%d",&y);
head->next=newnode(y);
head=head->next;
}
headlist=sort(headlist);
while(headlist!=NULL)
{
printf("%d ",headlist->data);
headlist=headlist->next;
}
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;
}
node* reverse(node* head)
{
node* prev=NULL,*nxt=NULL,*current=head;
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;
}
node* find_less(node* head)
{
node* curr=head;
node* mx=head,*temp;
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;
}
}
return head;
}
node* sort(node* head)
{
head=reverse(head);
head=find_less(head);
head=reverse(head);
return head;
}
int main()
{
int t;cin>>t;
while(t--)
{
int n;
cin>>n;
int x;cin>>x;
node* head=newnode(x);
node* headlist=head;
for(int i=1;i<n;i++)
{
int y;cin>>y;
head->next=newnode(y);
head=head->next;
}
headlist= sort(headlist);
while(headlist!=NULL)
{
cout<<headlist->data<<" ";
headlist=headlist->next;
}
cout<<"\n";
}
return 0;
}
import java.util.*;
import java.io.*;
class LinkedList {
Node head;
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
void delLesserNodes()
{
reverseList();
_delLesserNodes();
reverseList();
}
void _delLesserNodes()
{
Node current = head;
Node maxnode = head;
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);
new_node.next = head;
head = new_node;
}
void reverseList()
{
Node current = head;
Node prev = null;
Node next;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
}
void printList()
{
Node temp = head;
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();
LinkedList llist = new LinkedList();
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(); }
}
}
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node def printList(self): temp = self.head while(temp): print (temp.data,end=" ") temp = temp.next def reverse_it(self): prev = None curr = self.head while curr: next = curr.next curr.next = prev prev = curr curr = next self.head = prev return prev def find_less(self): head = self.head curr = head mx = head while curr and curr.next: if curr.next.data < mx.data: temp = curr.next curr.next = temp.next del temp else: curr = curr.next mx = curr self.head = head def sort(self): self.reverse_it() self.find_less() self.reverse_it() llist = LinkedList() llist.push(11) llist.push(18) llist.push(20) llist.push(14) llist.push(15) llist.printList() llist.sort() print() llist.printList()
Conclusion
In the above article, we clearly understood how small nodes and large nodes are different, we have also tried how to delete smaller nodes in linked list and delete larger nodes in linked list.To practice more problems on Linked lists you can check out MYCODE | Competitive Programming.
FAQs
1. What is the time complexity of deleting a node from the first in a linked list?
The time complexity of deleting a node from the first in a linked list is O(n).
2. What is the space complexity of deleting a linked list?
To delete a linked list we need a temporary and empty list to track the traversing. So, the space complexity is O(n).
3. What are the conditions for deleting a node in a linked list?
- Find the previous node to the node which is to be deleted.
- Change the next of the previous node.
- Free memory for the memory which is to be deleted.