Dada una lista enlazada que se ordena en función de valores absolutos. Ordene la lista según los valores reales.
Ejemplos:
Input: 1 -> -10 Output: -10 -> 1 Input: 1 -> -2 -> -3 -> 4 -> -5 Output: -5 -> -3 -> -2 -> 1 -> 4 Input: -5 -> -10 Output: -10 -> -5 Input: 5 -> 10 Output: 5 -> 10
Fuente: entrevista de Amazon
Una solución simple es recorrer la lista enlazada de principio a fin. Para cada Node visitado, verifique si está fuera de servicio. Si es así, retírelo de su posición actual e insértelo en la posición correcta. Esta es la implementación del ordenamiento por inserción para la lista enlazada y la complejidad temporal de esta solución es O(n*n).
Una mejor solución es ordenar la lista enlazada usando merge sort . La complejidad temporal de esta solución es O(n Log n).
Una solución eficiente puede funcionar en tiempo O(n). Una observación importante es que todos los elementos negativos están presentes en orden inverso. Entonces recorremos la lista, cada vez que encontramos un elemento que está fuera de servicio, lo movemos al frente de la lista enlazada.
A continuación se muestra la implementación de la idea anterior.
cada vez que encontramos un elemento que está fuera de servicio, lo movemos al frente de la lista enlazada.
A continuación se muestra la implementación de la idea anterior.
Javascript
<script>
// Javascript program to sort a linked list,
// already sorted by absolute values
// head of list
var head;
// Linked list Node
class Node
{
constructor(d)
{
this.data = d;
this.next = null;
}
}
// To sort a linked list by actual values.
// The list is assumed to be sorted by
// absolute values.
function sortedList(head)
{
// Initialize previous and current
// nodes
var prev = head;
var curr = head.next;
// Traverse list
while (curr != null)
{
// If curr is smaller than prev, then
// it must be moved to head
if (curr.data < prev.data)
{
// Detach curr from linked list
prev.next = curr.next;
// Move current node to beginning
curr.next = head;
head = curr;
// Update current
curr = prev;
}
// Nothing to do if current element
// is at right place
else
prev = curr;
// Move current
curr = curr.next;
}
return head;
}
/* Inserts a new Node at front of
the list. */
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 print linked list
function printList(head)
{
var temp = head;
while (temp != null)
{
document.write(temp.data + " ");
temp = temp.next;
}
document.write("<br/>");
}
// Driver code
/* Constructed Linked List is
1->2->3->4->5->6-> 7->8->8->
9->null */
push(-5);
push(5);
push(4);
push(3);
push(-2);
push(1);
push(0);
document.write(
"Original List :<br/>");
printList(head);
head = sortedList(head);
document.write(
"Sorted list :<br/>");
printList(head);
// This code is contributed by aashish1995
</script>
Producción:
Original list : 0 -> 1 -> -2 -> 3 -> 4 -> 5 -> -5 Sorted list : -5 -> -2 -> 0 -> 1 -> 3 -> 4 -> 5
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)
¡ Consulte el artículo completo sobre Ordenar lista enlazada que ya está ordenada en valores absolutos 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