Dada una lista enlazada individualmente, elimine todos los Nodes que tengan un valor mayor en el lado derecho.
Ejemplos:
a) La lista 12->15->10->11->5->6->2->3->NULL debe cambiarse a 15->11->6->3->NULL. Tenga en cuenta que se han eliminado 12, 10, 5 y 2 porque hay un valor mayor en el lado derecho.
Cuando examinamos 12, vemos que después de 12 hay un Node con un valor mayor que 12 (es decir, 15), por lo que eliminamos 12.
Cuando examinamos 15, no encontramos ningún Node después de 15 que tenga un valor mayor que 15, por lo que mantenemos este Node.
Cuando hacemos esto, obtenemos 15->6->3
b) La lista 10->20->30->40->50->60->NULL debe cambiarse a 60->NULL. Tenga en cuenta que se han eliminado 10, 20, 30, 40 y 50 porque todos tienen un valor mayor en el lado derecho.
c) La lista 60->50->40->30->20->10->
Método 1 (Simple)
Use dos bucles. En el bucle exterior, seleccione los Nodes de la lista vinculada uno por uno. En el bucle interno, verifique si existe un Node cuyo valor sea mayor que el Node seleccionado. Si existe un Node cuyo valor es mayor, elimine el Node seleccionado.
Complejidad del tiempo: O(n^2)
Método 2 (Uso inverso)
Gracias a Paras por proporcionar el siguiente algoritmo.
1. Invierta la lista.
2. Recorra la lista invertida. Mantenga el máximo hasta ahora. Si el siguiente Node es menor que max, elimine el siguiente Node; de lo contrario, max = next node.
3. Invierta la lista nuevamente para conservar el orden original.
Complejidad de tiempo: O(n)
Gracias a R.Srinivasan por proporcionar el código a continuación.
C++
// C++ program to delete nodes
// which have a greater value on
// right side
#include <bits/stdc++.h>
using namespace std;
/* structure of a linked list node */
struct Node
{
int data;
struct Node* next;
};
/* prototype for utility functions */
void reverseList(struct Node** headref);
void _delLesserNodes(struct Node* head);
/* Deletes nodes which have a node with
greater value node on left side */
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;
}
}
}
/* Utility function to insert a node
at the beginning */
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = *head_ref;
*head_ref = new_node;
}
/* Utility function to reverse a linked list */
void reverseList(struct Node** headref)
{
struct Node* current = *headref;
struct Node* prev = NULL;
struct Node* next;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*headref = prev;
}
/* Utility function to print a linked list */
void printList(struct Node* head)
{
while (head != NULL)
{
cout << " " << head->data ;
head = head->next;
}
cout << "\n" ;
}
/* Driver program to test above functions */
int main()
{
struct Node* head = NULL;
/* Create following linked list
12->15->10->11->5->6->2->3 */
push(&head, 3);
push(&head, 2);
push(&head, 6);
push(&head, 5);
push(&head, 11);
push(&head, 10);
push(&head, 15);
push(&head, 12);
cout << "Given Linked List \n" ;
printList(head);
delLesserNodes(&head);
cout << "Modified Linked List \n" ;
printList(head);
return 0;
}
// This code is contributed by shivanisinghss2110
C
// C program to delete nodes which have a greater value on
// right side
#include <stdio.h>
#include <stdlib.h>
/* structure of a linked list node */
struct Node {
int data;
struct Node* next;
};
/* prototype for utility functions */
void reverseList(struct Node** headref);
void _delLesserNodes(struct Node* head);
/* Deletes nodes which have a node with greater value node
on left side */
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;
}
}
}
/* Utility function to insert a node at the beginning */
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = *head_ref;
*head_ref = new_node;
}
/* Utility function to reverse a linked list */
void reverseList(struct Node** headref)
{
struct Node* current = *headref;
struct Node* prev = NULL;
struct Node* next;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*headref = prev;
}
/* Utility function to print a linked list */
void printList(struct Node* head)
{
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
/* Driver program to test above functions */
int main()
{
struct Node* head = NULL;
/* Create following linked list
12->15->10->11->5->6->2->3 */
push(&head, 3);
push(&head, 2);
push(&head, 6);
push(&head, 5);
push(&head, 11);
push(&head, 10);
push(&head, 15);
push(&head, 12);
printf("Given Linked List \n");
printList(head);
delLesserNodes(&head);
printf("Modified Linked List \n");
printList(head);
return 0;
}
Java
// Java program to delete nodes which have a greater value on
// right side
class LinkedList {
Node head; // head of list
/* Linked list Node*/
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
/* Deletes nodes which have a node with greater
value node on left side */
void delLesserNodes()
{
/* 1.Reverse the linked list */
reverseList();
/* 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();
/* 3) Reverse the linked list again to retain
the original order */
reverseList();
}
/* Deletes nodes which have greater value node(s)
on left side */
void _delLesserNodes()
{
Node current = head;
/* Initialise max */
Node maxnode = head;
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;
temp = null;
}
/* If current is greater than max, then update
max and move current */
else {
current = current.next;
maxnode = current;
}
}
}
/* Utility functions */
/* Inserts a new Node at front of the list. */
void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Function to reverse the linked list */
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;
}
/* Function to print linked list */
void printList()
{
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
/* Driver program to test above functions */
public static void main(String args[])
{
LinkedList llist = new LinkedList();
/* Constructed Linked List is 12->15->10->11->
5->6->2->3 */
llist.push(3);
llist.push(2);
llist.push(6);
llist.push(5);
llist.push(11);
llist.push(10);
llist.push(15);
llist.push(12);
System.out.println("Given Linked List");
llist.printList();
llist.delLesserNodes();
System.out.println("Modified Linked List");
llist.printList();
}
} /* This code is contributed by Rajat Mishra */
C#
// C# program to delete nodes which have a greater value on
// right side
using System;
class LinkedList
{
public Node head; // head of list
/* Linked list Node*/
public class Node
{
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
/* Deletes nodes which have a node with greater
value node on left side */
void delLesserNodes()
{
/* 1.Reverse the linked list */
reverseList();
/* 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();
/* 3) Reverse the linked list again to retain
the original order */
reverseList();
}
/* Deletes nodes which have greater value node(s)
on left side */
void _delLesserNodes()
{
Node current = head;
/* Initialise max */
Node maxnode = head;
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;
temp = null;
}
/* If current is greater than max, then update
max and move current */
else
{
current = current.next;
maxnode = current;
}
}
}
/* Utility functions */
/* Inserts a new Node at front of the list. */
void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Function to reverse the linked list */
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;
}
/* Function to print linked list */
void printList()
{
Node temp = head;
while (temp != null)
{
Console.Write(temp.data + " ");
temp = temp.next;
}
Console.WriteLine();
}
/* Driver program to test above functions */
public static void Main(string []args)
{
LinkedList llist = new LinkedList();
/* Constructed Linked List is 12->15->10->11->
5->6->2->3 */
llist.push(3);
llist.push(2);
llist.push(6);
llist.push(5);
llist.push(11);
llist.push(10);
llist.push(15);
llist.push(12);
Console.WriteLine("Given Linked List");
llist.printList();
llist.delLesserNodes();
Console.WriteLine("Modified Linked List");
llist.printList();
}
}
// This code is contributed by pratham76
Javascript
<script>
// javascript program to delete nodes which have a greater value on
// right side
var head; // head of list
/* Linked list Node */
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
/*
* Deletes nodes which have a node with greater value node on left side
*/
function delLesserNodes() {
/* 1.Reverse the linked list */
reverseList();
/*
* 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();
/*
* 3) Reverse the linked list again to retain the original order
*/
reverseList();
}
/*
* Deletes nodes which have greater value node(s) on left side
*/
function _delLesserNodes() {
var current = head;
/* Initialise max */
var maxnode = head;
var 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;
temp = null;
}
/*
* If current is greater than max, then update max and move current
*/
else {
current = current.next;
maxnode = current;
}
}
}
/* Utility functions */
/* Inserts a new Node at front of the */
function push(new_data) {
/*
* 1 & 2: Allocate the Node & Put in the data
*/
var new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Function to reverse the linked list */
function reverseList() {
var current = head;
var prev = null;
var next;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
}
/* Function to print linked list */
function printList() {
var temp = head;
while (temp != null) {
document.write(temp.data + " ");
temp = temp.next;
}
document.write();
}
/* Driver program to test above functions */
/*
* Constructed Linked List is 12->15->10->11-> 5->6->2->3
*/
push(3);
push(2);
push(6);
push(5);
push(11);
push(10);
push(15);
push(12);
document.write("Given Linked List<br/>");
printList();
delLesserNodes();
document.write("<br/>Modified Linked List<br/>");
printList();
// This code contributed by aashish1995
</script>
Producción
Given Linked List 12 15 10 11 5 6 2 3 Modified Linked List 15 11 6 3
Complejidad de tiempo : O(n) donde n no es ningún Node en la lista Vinculada
Espacio Auxiliar: O(n)
Método 3:
El otro método más simple es recorrer la lista desde el principio y eliminar el Node cuando el Node actual < siguiente Node. Para eliminar el Node actual, siga este enfoque.
Supongamos que tiene que eliminar el Node actual X
1. Copie los datos del siguiente Node en X, es decir, X.data = X.next.data
2. Copie la siguiente dirección del Node siguiente, es decir, X.next = X.next.next;
Avanzar en la lista solo cuando el Node actual sea > el siguiente Node.
Java
// Java program for above approach
import java.io.*;
// This class represents a single node
// in a linked list
class Node {
int data;
Node next;
public Node(int data){
this.data = data;
this.next = null;
}
}
//This is a utility class for linked list
class LLUtil{
// This function creates a linked list from a
// given array and returns head
public Node createLL(int[] arr){
Node head = new Node(arr[0]);
Node temp = head;
Node newNode = null;
for(int i = 1; i < arr.length; i++){
newNode = new Node(arr[i]);
temp.next = newNode;
temp = temp.next;
}
return head;
}
//This function prints given linked list
public void printLL(Node head){
while(head != null){
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
}
class GFG {
public static void main (String[] args) {
int[] arr = {12,15,10,11,5,6,2,3};
LLUtil llu = new LLUtil();
Node head = llu.createLL(arr);
System.out.println("Given Linked List");
llu.printLL(head);
head = deleteNodesOnRightSide(head);
System.out.println("Modified Linked List");
llu.printLL(head);
}
//Main function
public static Node deleteNodesOnRightSide(Node head){
if(head == null || head.next == null) return head;
Node nextNode = deleteNodesOnRightSide(head.next);
if(nextNode.data > head.data) return nextNode;
head.next = nextNode;
return head;
}
}
C#
// C# program for above approach
using System;
// This class represents a single node
// in a linked list
class Node
{
public int data;
public Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
// This is a utility class for linked list
class LLUtil
{
// This function creates a linked list
// from a given array and returns head
public Node createLL(int[] arr)
{
Node head = new Node(arr[0]);
Node temp = head;
Node newNode = null;
for(int i = 1; i < arr.Length; i++)
{
newNode = new Node(arr[i]);
temp.next = newNode;
temp = temp.next;
}
return head;
}
// This function prints given linked list
public void printLL(Node head)
{
while (head != null)
{
Console.Write(head.data + " ");
head = head.next;
}
Console.WriteLine();
}
}
class GFG{
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 12, 15, 10, 11, 5, 6, 2, 3 };
LLUtil llu = new LLUtil();
Node head = llu.createLL(arr);
Console.WriteLine("Given Linked List");
llu.printLL(head);
deleteNodesOnRightSide(head);
Console.WriteLine("Modified Linked List");
llu.printLL(head);
}
// Main function
public static void deleteNodesOnRightSide(Node head)
{
Node temp = head;
while (temp != null && temp.next != null)
{
// Copying next node data into current node
// i.e. we are indirectly deleting current node
if (temp.data < temp.next.data)
{
temp.data = temp.next.data;
temp.next = temp.next.next;
}
else
{
// Move to the next node
temp = temp.next;
}
}
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// javascript program for above approach// This class represents a single node
// in a linked list
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
// This is a utility class for linked list
// This function creates a linked list from a
// given array and returns head
function createLL(arr) {
var head = new Node(arr[0]);
var temp = head;
var newNode = null;
for (i = 1; i < arr.length; i++) {
newNode = new Node(arr[i]);
temp.next = newNode;
temp = temp.next;
}
return head;
}
// This function prints given linked list
function printLL(head) {
while (head != null) {
document.write(head.data + " ");
head = head.next;
}
document.write("<br/>");
}
// Main function
function deleteNodesOnRightSide(head) {
if (head == null || head.next == null)
return head;
var nextNode = deleteNodesOnRightSide(head.next);
if (nextNode.data > head.data)
return nextNode;
head.next = nextNode;
return head;
}
var arr = [ 12, 15, 10, 11, 5, 6, 2, 3 ];
var head = createLL(arr);
document.write("Given Linked List<br/>");
printLL(head);
head = deleteNodesOnRightSide(head);
document.write("<br/>Modified Linked List<br/>");
printLL(head);
// This code contributed by aashish1995
</script>
Producción
Given Linked List 12 15 10 11 5 6 2 3 Modified Linked List 15 11 6 3
Complejidad de tiempo : O(n) donde n no es ningún Node en la lista Vinculada
Espacio Auxiliar: O(1)
Fuente:
Escriba comentarios si encuentra que el código/algoritmo anterior es incorrecto o encuentra otras formas de resolver el mismo problema.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA