Dada una lista enlazada. La lista enlazada está en orden ascendente y descendente alternado. Ordena la lista de manera eficiente.
Ejemplo:
Input List: 10 -> 40 -> 53 -> 30 -> 67 -> 12 -> 89 -> NULL Output List: 10 -> 12 -> 30 -> 40 -> 53 -> 67 -> 89 -> NULL Input List: 1 -> 4 -> 3 -> 2 -> 5 -> NULL Output List: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
Solución simple:
Enfoque: La idea básica es aplicar la ordenación por fusión en la lista enlazada.
La implementación se analiza en este artículo: Merge Sort for Linked List .
Análisis de Complejidad:
- Complejidad de tiempo: el tipo de combinación de lista enlazada toma O (n log n) tiempo. En el árbol de clasificación por fusión, la altura es log n. Ordenar cada nivel tomará O(n) tiempo. Entonces la complejidad del tiempo es O (n log n).
- Espacio auxiliar: O (n log n), en el árbol de ordenación por combinación, la altura es log n. Almacenar cada nivel ocupará O(n) espacio. Entonces la complejidad del espacio es O (n log n).
Solución eficiente:
Enfoque:
- Separa dos listas.
- Invertir el uno con orden descendente
- Combinar ambas listas.
Diagrama:
A continuación se muestran las implementaciones del algoritmo anterior:
Java
// Java program to sort a linked list // that is alternatively sorted in // increasing and decreasing order class LinkedList { // head of list Node head; // Linked list Node class Node { int data; Node next; Node(int d) { data = d; next = null; } } Node newNode(int key) { return new Node(key); } /* This is the main function that sorts the linked list.*/ void sort() { /* Create 2 dummy nodes and initialise as heads of linked lists */ Node Ahead = new Node(0), Dhead = new Node(0); // Split the list into lists splitList(Ahead, Dhead); Ahead = Ahead.next; Dhead = Dhead.next; // Reverse the descending list Dhead = reverseList(Dhead); // Merge the 2 linked lists head = mergeList(Ahead, Dhead); } // Function to reverse the linked list Node reverseList(Node Dhead) { Node current = Dhead; Node prev = null; Node next; while (current != null) { next = current.next; current.next = prev; prev = current; current = next; } Dhead = prev; return Dhead; } // Function to print linked list void printList() { Node temp = head; while (temp != null) { System.out.print(temp.data + " "); temp = temp.next; } System.out.println(); } // A utility function to merge // two sorted linked lists Node mergeList(Node head1, Node head2) { // Base cases if (head1 == null) return head2; if (head2 == null) return head1; Node temp = null; if (head1.data < head2.data) { temp = head1; head1.next = mergeList(head1.next, head2); } else { temp = head2; head2.next = mergeList(head1, head2.next); } return temp; } // This function alternatively splits // a linked list with head as head into two: // For example, 10->20->30->15->40->7 is // splitted into 10->30->40 and 20->15->7 // "Ahead" is reference to head of ascending // linked list // "Dhead" is reference to head of descending // linked list void splitList(Node Ahead, Node Dhead) { Node ascn = Ahead; Node dscn = Dhead; Node curr = head; // Link alternate nodes while (curr != null) { // Link alternate nodes in // ascending order ascn.next = curr; ascn = ascn.next; curr = curr.next; if (curr != null) { dscn.next = curr; dscn = dscn.next; curr = curr.next; } } ascn.next = null; dscn.next = null; } // Driver code public static void main(String args[]) { LinkedList llist = new LinkedList(); llist.head = llist.newNode(10); llist.head.next = llist.newNode(40); llist.head.next.next = llist.newNode(53); llist.head.next.next.next = llist.newNode(30); llist.head.next.next.next.next = llist.newNode(67); llist.head.next.next.next.next.next = llist.newNode(12); llist.head.next.next.next.next.next.next = llist.newNode(89); System.out.println("Given linked list"); llist.printList(); llist.sort(); System.out.println("Sorted linked list"); llist.printList(); } } // This code is contributed by Rajat Mishra
Producción:
Given Linked List is 10 40 53 30 67 12 89 Sorted Linked List is 10 12 30 40 53 67 89
Análisis de Complejidad:
- Complejidad temporal: O(n).
Se necesita un recorrido para separar la lista e invertirla. La fusión de listas ordenadas toma O(n) tiempo. - Espacio Auxiliar: O(1).
No se requiere espacio adicional.
Consulte el artículo completo sobre ¿Ordenar una lista vinculada que se ordena alternando órdenes ascendentes y descendentes? ¡para 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