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.
Javascript
<script>
// JavaScript Program to sort a
// linked list 0s, 1s
// or 2s by changing links
class Node
{
constructor(val)
{
this.data = val;
this.next = null;
}
}
// Sort a linked list of 0s, 1s
// and 2s by changing pointers.
function sortList(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
// a function many null checks.
var zeroD = new Node(0);
var oneD = new Node(0);
var twoD = new Node(0);
// Initialize current pointers for
// three lists and whole list.
var zero = zeroD, one = oneD,
two = twoD;
// Traverse list
var 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
function newNode(data)
{
// Allocating space
var newNode = new Node(data);
newNode.next = null;
return newNode;
}
// Function to print linked list
function printList(node)
{
while (node != null)
{
document.write(node.data + " ");
node = node.next;
}
}
var head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(0);
head.next.next.next = new Node(1);
document.write(
"Linked List Before Sorting<br/>");
printList(head);
head = sortList(head);
document.write(
"<br/>Linked List After Sorting<br/>");
printList(head);
// This code is contributed by gauravrajput1
</script>
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