Dada una lista enlazada individualmente, elimine todos los Nodes que tienen un valor mayor en el lado derecho.
Ejemplos:
Input: 12->15->10->11->5->6->2->3->NULL
Output: 15->11->6->3->NULL
Explanation: 12, 10, 5 and 2 have been deleted because there is a
greater value on the right side. When we examine 12,
we see that after 12 there is one node with a value
greater than 12 (i.e. 15), so we delete 12. When we
examine 15, we find no node after 15 that has a value
greater than 15, so we keep this node. When we go like
this, we get 15->6->3
Input: 10->20->30->40->50->60->NULL
Output: 60->NULL
Explanation: 10, 20, 30, 40, and 50 have been deleted because
they all have a greater value on the right side.
Input: 60->50->40->30->20->10->NULL
Output: No Change.
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 elegido.
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.
Javascript
<script>
// Javascript program to delete nodes which
// have a greater value on right side
// head of list
var head;
// 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 code
/* 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 is 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)
Espacio Auxiliar: O(1)
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:
- Copie los datos del siguiente Node en X, es decir, X.data = X.next.data.
- Copie la siguiente dirección del siguiente Node, es decir, X.next = X.next.next.
Avanzar en la lista solo cuando el Node actual sea > el siguiente Node.
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 is 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)
Espacio Auxiliar: O(1)
Consulte el artículo completo sobre Eliminar Nodes que tienen un valor mayor en el lado derecho para obtener más detalles.
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