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.
C++
// C++ program to sort a linked list, // already sorted by absolute values #include <bits/stdc++.h> using namespace std; // Linked List Node struct Node { Node* next; int data; }; // Utility function to insert a // node at the beginning void push(Node** head, int data) { Node* newNode = new Node; newNode->next = (*head); newNode->data = data; (*head) = newNode; } // Utility function to print // a linked list void printList(Node* head) { while (head != NULL) { cout << head->data; if (head->next != NULL) cout << " -> "; head = head->next; } cout<<endl; } // To sort a linked list by actual values. // The list is assumed to be sorted by // absolute values. void sortList(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; } } // Driver code int main() { Node* head = NULL; push(&head, -5); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, -2); push(&head, 1); push(&head, 0); cout << "Original list :"; printList(head); sortList(&head); cout << "Sorted list :"; printList(head); return 0; }
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