Dada una lista enlazada de 0, 1 y 2, ordénela.
Ejemplos :
Input: 1 -> 1 -> 2 -> 0 -> 2 -> 0 -> 1 -> NULL Output: 0 -> 0 -> 1 -> 1 -> 1 -> 2 -> 2 -> NULL Input: 1 -> 1 -> 2 -> 1 -> 0 -> NULL Output: 0 -> 1 -> 1 -> 1 -> 2 -> NULL
Fuente: Entrevista de Microsoft | Serie 1
Los siguientes pasos se pueden utilizar para ordenar la lista vinculada dada.
- Recorra la lista y cuente el número de 0, 1 y 2. Sean los conteos n1, n2 y n3 respectivamente.
- Recorra la lista nuevamente, complete los primeros n1 Nodes con 0, luego n2 Nodes con 1 y finalmente n3 Nodes con 2.
La imagen de abajo es una ejecución en seco del enfoque anterior:
A continuación se muestra la implementación del enfoque anterior:
C
// C Program to sort a linked list
// 0s, 1s or 2s
#include<stdio.h>
#include<stdlib.h>
// Link list node
struct Node
{
int data;
struct Node* next;
};
// Function to sort a linked list
// of 0s, 1s and 2s
void sortList(struct Node *head)
{
// Initialize count of '0', '1'
// and '2' as 0
int count[3] = {0, 0, 0};
struct Node *ptr = head;
/* Count total number of '0', '1' and '2'
count[0] will store total number of '0's
count[1] will store total number of '1's
count[2] will store total number of '2's */
while (ptr != NULL)
{
count[ptr->data] += 1;
ptr = ptr->next;
}
int i = 0;
ptr = head;
/* Let say count[0] = n1, count[1] = n2 and
count[2] = n3
now start traversing list from head node,
1) fill the list with 0, till n1 > 0
2) fill the list with 1, till n2 > 0
3) fill the list with 2, till n3 > 0 */
while (ptr != NULL)
{
if (count[i] == 0)
++i;
else
{
ptr->data = i;
--count[i];
ptr = ptr->next;
}
}
}
// Function to push a node
void push (struct Node** head_ref,
int new_data)
{
// Allocate node
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
// Put in the data
new_node->data = new_data;
// Link the old list off the new node
new_node->next = (*head_ref);
// Move the head to point to the
// new node
(*head_ref) = new_node;
}
// Function to print linked list
void printList(struct Node *node)
{
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
printf("n");
}
// Driver code
int main(void)
{
struct Node *head = NULL;
push(&head, 0);
push(&head, 1);
push(&head, 0);
push(&head, 2);
push(&head, 1);
push(&head, 1);
push(&head, 2);
push(&head, 1);
push(&head, 2);
printf(
"Linked List Before Sorting");
printList(head);
sortList(head);
printf(
"Linked List After Sorting");
printList(head);
return 0;
}
Producción:
Linked List Before Sorting 2 1 2 1 1 2 0 1 0 Linked List After Sorting 0 0 1 1 1 1 2 2 2
Complejidad de tiempo: O(n) donde n es el número de Nodes en la lista enlazada.
Espacio Auxiliar: O(1)
Consulte el artículo completo sobre Ordenar una lista enlazada de 0, 1 y 2 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