2

Tengo el siguiente código, que funciona pero no sería lo correcto, ya que debería ordenar la lista que se crea, y devolver el ordenamiento en la misma. Aca estoy devolviendo en una lista nueva.

Como se puede modificar?

LinkedList.prototype.sortList = function () {
  // Tu código aca:
  let current = this.head; // el auxiliar apunta a la cabecera
  let aux;
  let prev = null;
  if (!this.head) return false; //si la lista está vacía retorna null

while(current){
  array.push(current.value)
  current = current.next;
}
 array.sort((a, b) => {
  if(a > b) return -1;
});
for(let i = 0; i < array.length; i++){
  newList.add(array[i]);
}
return newList;
}

2
  • De dónde sale newList, cuál es la lista que deberías devolver?
    – Sr1871
    Commented el 16 oct. 2022 a las 0:46
  • Por favor, aclara tu problema específico o proporciona detalles adicionales para resaltar exactamente lo que necesitas. Tal como está escrito, es difícil saber exactamente qué estás preguntando.
    – Comunidad Bot
    Commented el 16 oct. 2022 a las 10:34

1 respuesta 1

0

Veo que estás intentando ordenar una lista encadenada y lo que deseas es que quede ordenada en la propia lista.

Lo que has intentado hacer es pasar toda la lista a un array, ordenar el array y luego volver a crear una lista a partir de este array. Esto, evidentemente no es óptimo e invalida prácticamente las ventajas que proporciona un lista encadenada. Lo ideal es ordenar directamente sobre la propia lista (nota, para hacer ordenaciones lo mejor sería que fuese una lista doblemente encadenada, pero en este caso voy a suponer que no lo es).

Para ordenarla existen distintos algoritmos, pero en el código que te expongo lo que he hecho es recorrer la lista e intercambiar aquellos valores que están desordenados, dos a dos. Este proceso se repite hasta que no se realiza ningún intercambio, momento en el cual la lista ya se encuentra ordenada. Espero que el código sea lo suficientemente claro como para que se entienda fácilmente.

LinkedList.prototype.sortList = function () {
  let flagCambio = true;

  if(this.head == null) return; // La lista está vacía, no hay nada que ordenar.

  while(flagCambio){
    flagCambio = false;
    let current = this.head;
    while(current.next != null){
      if(current.value > current.next.value){
        let temp = current.value;
        current.value = current.next.value;
        current.next.value = temp;
        flagCambio = true;  // Se ha realizado al menos un cambio, así que activamos el flag.
      }
      current = current.next;
    }
  }

  // Al llegar aquí se ha recorrido toda la lista sin hacer ningún cambio, así que ya está ordenada.
}

Por otro lado, he intercambiado los valores de cada nodo cuando estos están desordenados. En un caso real (con nodos grandes), lo ideal sería intercambiar los links entre los nodos, pero como eso complica un poquito el código ya que hay que mantener un puntero al nodo anterior, controlando si el nodo primero es el head, he preferido no hacerlo para que sea fácil de entender el código. Esto se evitaría si se usa una lista doblemente encadenada, como comenté más arriba.

Espero que te sea de ayuda.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.