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.
Java
// Java Program to sort a linked list
// 0s, 1s or 2s by changing links
public class Sort012
{
// Sort a linked list of 0s, 1s
// and 2s by changing pointers.
public static Node sortList(Node head)
{
if(head==null || head.next==null)
{
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 = new Node(0);
Node oneD = new Node(0);
Node twoD = new Node(0);
// Initialize current pointers for three
// lists and whole list.
Node zero = zeroD, one = oneD, two = twoD;
// Traverse list
Node curr = head;
while (curr!=null)
{
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!=null) ?
(oneD.next) : (twoD.next);
one.next = twoD.next;
two.next = null;
// Updated head
head = zeroD.next;
return head;
}
// Function to create and return a node
public static Node newNode(int data)
{
// Allocating space
Node newNode = new Node(data);
newNode.next = null;
return newNode;
}
// Function to print linked list
public static void printList(Node node)
{
while (node != null)
{
System.out.print(node.data+" ");
node = node.next;
}
}
Driver code
public static void main(String args[])
{
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(0);
head.next.next.next = new Node(1);
System.out.println(
"Linked List Before Sorting");
printList(head);
head = sortList(head);
System.out.println(
"Linked List After Sorting");
printList(head);
}
}
class Node
{
int data;
Node next;
Node(int data)
{
this.data=data;
}
}
//This code is contributed by Gaurav Tiwari
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