Dada una lista enlazada de 0, 1 y 2, ordénela.
Ejemplos:
Input: 2->1->2->1->1->2->0->1->0 Output: 0->0->1->1->1->1->2->2->2 The sorted Array is 0, 0, 1, 1, 1, 1, 2, 2, 2. Input: 2->1->0 Output: 0->1->2 The sorted Array is 0, 1, 2
Método 1: hay una solución discutida en la publicación a continuación que funciona cambiando los datos de los Nodes.
Ordenar una lista enlazada de 0, 1 y 2
La solución anterior no funciona cuando estos valores tienen datos asociados con ellos.
Por ejemplo, estos tres representan tres colores y diferentes tipos de objetos asociados con los colores y clasifican los objetos (conectados con una lista vinculada) en función de los colores.
Método 2: en esta publicación, se analiza una nueva solución que funciona cambiando los enlaces.
Enfoque: Iterar a través de la lista enlazada. Mantenga 3 punteros llamados cero, uno y dos para apuntar a los Nodes finales actuales de las listas vinculadas que contienen 0, 1 y 2 respectivamente. Para cada Node recorrido, lo adjuntamos al final de su lista correspondiente. Finalmente, vinculamos las tres listas. Para evitar muchas verificaciones nulas, usamos tres punteros ficticios zeroD, oneD y twoD que funcionan como encabezados ficticios de tres listas.
C++
// C++ Program to sort a linked list
// 0s, 1s or 2s by changing links
#include <bits/stdc++.h>
// Link list node
struct Node
{
int data;
struct Node* next;
};
Node* newNode(int data);
// Sort a linked list of 0s, 1s
// and 2s by changing pointers.
Node* sortList(Node* head)
{
if (!head || !(head->next))
return head;
// Create three dummy nodes to point
// to beginning of three linked lists.
// These dummy nodes are created to
// avoid many null checks.
Node* zeroD = newNode(0);
Node* oneD = newNode(0);
Node* twoD = newNode(0);
// Initialize current pointers for
// three lists and whole list.
Node* zero = zeroD, *one = oneD,
*two = twoD;
// Traverse list
Node* curr = head;
while (curr)
{
if (curr->data == 0)
{
zero->next = curr;
zero = zero->next;
curr = curr->next;
}
else if (curr->data == 1)
{
one->next = curr;
one = one->next;
curr = curr->next;
}
else
{
two->next = curr;
two = two->next;
curr = curr->next;
}
}
// Attach three lists
zero->next = (oneD->next) ?
(oneD->next) : (twoD->next);
one->next = twoD->next;
two->next = NULL;
// Updated head
head = zeroD->next;
// Delete dummy nodes
delete zeroD;
delete oneD;
delete twoD;
return head;
}
// Function to create and return a node
Node* newNode(int data)
{
// Allocating space
Node* newNode = new Node;
// Inserting the required data
newNode->data = data;
newNode->next = NULL;
}
// Function to print linked list
void printList(struct Node* node)
{
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
printf("");
}
// Driver code
int main(void)
{
// Creating the list 1->2->4->5
Node* head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(0);
head->next->next->next = newNode(1);
printf("Linked List Before Sorting");
printList(head);
head = sortList(head);
printf("Linked List After Sorting");
printList(head);
return 0;
}
Producción :
Linked List Before Sorting 1 2 0 1 Linked List After Sorting 0 1 1 2
Análisis de Complejidad:
- Complejidad de tiempo: O(n) donde n es un número de Nodes en la lista enlazada.
Solo se necesita un recorrido de la lista enlazada. - Espacio Auxiliar: O(1).
Como no se requiere espacio adicional.
Consulte el artículo completo sobre Ordenar una lista enlazada de 0, 1 y 2 cambiando los enlaces 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