DELETE NODES FROM LINKED LIST

Concepts Used

Linked lists,reverse a linked list

Difficulty Level

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

Explanation:

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

[forminator_quiz id="1803"]

This article tried to discuss the concepts of Linked lists. Hope this blog helps you understand and solve the problem. To practice more problems on Linked lists you can check out MYCODE | Competitive Programming

Leave a Reply

Your email address will not be published. Required fields are marked *