← Estructuras de datos desde cero · Lección 11/32
Borrar, invertir y mezclar
Borrar es saltarse un nodo
Para sacar un nodo de en medio no se mueve nada: el nodo anterior deja de apuntarle y apunta al que sigue. anterior.siguiente = anterior.siguiente.siguiente. El nodo saltado queda sin nadie que lo apunte y JavaScript lo recoge solo.
El caso raro es la cabeza, que no tiene anterior. Un truco muy usado es poner un nodo falso antes de la cabeza (un *centinela*, o *dummy*): así todos los nodos tienen anterior y el código no necesita un caso especial.
$ node leccion.js
Pulsa CORRER (o Ctrl+Enter).
Qué mirar
Las tres salen bien con el mismo código: borrar en medio, borrar la cabeza y dejar la lista vacía. Sin el centinela, los dos últimos casos necesitarían un if aparte.
Toda la lección en una página
Borrar es saltarse un nodo
Para sacar un nodo de en medio no se mueve nada: el nodo anterior deja de apuntarle y apunta al que sigue. anterior.siguiente = anterior.siguiente.siguiente. El nodo saltado queda sin nadie que lo apunte y JavaScript lo recoge solo.
El caso raro es la cabeza, que no tiene anterior. Un truco muy usado es poner un nodo falso antes de la cabeza (un *centinela*, o *dummy*): así todos los nodos tienen anterior y el código no necesita un caso especial.
class Nodo {
constructor(valor, siguiente = null) { this.valor = valor; this.siguiente = siguiente; }
}
const desde = arr => arr.reduceRight((sig, v) => new Nodo(v, sig), null);
const ver = c => { const r = []; for (; c; c = c.siguiente) r.push(c.valor); return r.join(" -> ") || "(vacía)"; };
function borrar(cabeza, x) {
const falso = new Nodo(null, cabeza); // centinela antes de la cabeza
let anterior = falso;
while (anterior.siguiente !== null) {
if (anterior.siguiente.valor === x) {
anterior.siguiente = anterior.siguiente.siguiente; // saltarlo
break;
}
anterior = anterior.siguiente;
}
return falso.siguiente; // la cabeza (quizá nueva)
}
console.log(ver(borrar(desde([3, 8, 5]), 8)));
console.log(ver(borrar(desde([3, 8, 5]), 3)));
console.log(ver(borrar(desde([3]), 3)));
Las tres salen bien con el mismo código: borrar en medio, borrar la cabeza y dejar la lista vacía. Sin el centinela, los dos últimos casos necesitarían un if aparte.
Invertir: voltear cada flecha
Invertir una lista no copia nada: voltea cada flecha. Se camina con tres punteros:
anterior: lo que ya quedó volteado (empieza ennull).actual: el nodo que toca voltear.siguiente: se guarda antes de voltear, porque al cambiaractual.siguientese pierde el camino.
En cada paso, actual pasa a apuntar a anterior, y los tres avanzan. Al final, anterior es la cabeza nueva. O(n) y sin memoria extra. Es uno de los retos de entrevista más famosos.
class Nodo {
constructor(valor, siguiente = null) { this.valor = valor; this.siguiente = siguiente; }
}
const desde = arr => arr.reduceRight((sig, v) => new Nodo(v, sig), null);
const ver = c => { const r = []; for (; c; c = c.siguiente) r.push(c.valor); return r.join(" -> "); };
function invertir(cabeza) {
let anterior = null, actual = cabeza;
while (actual !== null) {
const siguiente = actual.siguiente; // guardar el camino
actual.siguiente = anterior; // voltear la flecha
anterior = actual; // avanzar los tres
actual = siguiente;
console.log(" volteado:", ver(anterior), "| falta:", ver(actual) || "nada");
}
return anterior;
}
console.log(ver(invertir(desde([1, 2, 3, 4]))));
En cada vuelta la parte volteada crece por delante (1, luego 2 -> 1, luego 3 -> 2 -> 1…) y lo que falta se encoge. Al final queda 4 -> 3 -> 2 -> 1.
Mezclar dos listas ordenadas
Si tienes dos listas ya ordenadas, juntarlas en una sola ordenada es como dos filas que se vuelven una: comparas los dos primeros, tomas el más chico y avanzas en esa lista. Cuando una se acaba, la otra se cuelga entera al final.
Con un nodo centinela al principio, el código queda corto. Es O(n + m) y no crea nodos nuevos: sólo reacomoda flechas. Esta mezcla es la mitad de merge sort, que vas a ver en recursión.
class Nodo {
constructor(valor, siguiente = null) { this.valor = valor; this.siguiente = siguiente; }
}
const desde = arr => arr.reduceRight((sig, v) => new Nodo(v, sig), null);
const ver = c => { const r = []; for (; c; c = c.siguiente) r.push(c.valor); return r.join(" -> "); };
function mezclar(a, b) {
const falso = new Nodo(null);
let fin = falso;
while (a !== null && b !== null) {
if (a.valor <= b.valor) { fin.siguiente = a; a = a.siguiente; }
else { fin.siguiente = b; b = b.siguiente; }
fin = fin.siguiente;
}
fin.siguiente = a !== null ? a : b; // lo que sobre, entero
return falso.siguiente;
}
console.log(ver(mezclar(desde([1, 4, 9]), desde([2, 3, 10, 12]))));
Se van tomando 1, 2, 3, 4, 9; ahí la primera lista se acaba y «10 -> 12» se cuelga tal cual, sin compararlo.