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.
Java
// Java program to sort a linked list,
// already sorted by absolute values
class SortList
{
// Head of list
static Node head;
// Linked list Node
static class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
// To sort a linked list by actual values.
// The list is assumed to be sorted by
// absolute values.
Node sortedList(Node head)
{
// Initialize previous and current
// nodes
Node prev = head;
Node 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. */
public 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 print linked list
void printList(Node head)
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
// Driver code
public static void main(String args[])
{
SortList llist = new SortList();
/* Constructed Linked List is
1->2->3->4->5->6->
7->8->8->9->null */
llist.push(-5);
llist.push(5);
llist.push(4);
llist.push(3);
llist.push(-2);
llist.push(1);
llist.push(0);
System.out.println("Original List :");
llist.printList(llist.head);
llist.head = llist.sortedList(head);
System.out.println("Sorted list :");
llist.printList(llist.head);
}
}
// This code is contributed by Amit Khandelwal(Amit Khandelwal 1).
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