Listas vinculadas recursivas en Java

Question

Estoy trabajando en una tarea que me obliga a escribir un programa java para imprimir en orden inverso los datos contenidos en una lista vinculada utilizando recursividad. Hasta ahora esto es lo que tengo, funciona pero solo en el elemento final en la lista IE. se detiene una vez que imprime el último elemento.

public String reverse(IntNode head){ 
     String result = ""; 
     if(head.getLink() == null){ 
      result += head.getData(); 
      return result; 
     } 

     else if(head.getLink().getLink() == null){ 
      result += head.getLink().getData(); 
      head.removeNodeAfter(); 
      return result; 
     } 

     else{ 
      return reverse(head.getLink()); 
     } 
    } 

¿Cómo haré para seguir la lista hacia atrás en el árbol recursivo?

Answer 1

Este código es más complicado de lo que debe ser. En este caso, la recursividad puede ser dividido en 2 casos (o 2 rutas de ejecución de la función podría tener):

1. caso recursivo: este camino llama a sí misma de manera que la recursividad puede iniciar (o continuar)
2. caso base: este camino termina la recursión mediante la devolución sin que se hace llamar

el código tiene 2 casos base, y sólo se necesita 1. Piense en todas las diferentes entradas puede llamar a la función con:

1. head es null

2. head es un IntNode:

   a. head.getLink() devuelve null

   b. head.getLink() devuelve un IntNode:

   1. head.getLink().getLink() vuelve null

   2. head.getLink().getLink() devuelve un IntNode

Vamos a empezar a notar un patrón; una vez que se simplifica en realidad sólo hay 2 entradas posibles:

1. head es null
2. head es un IntNode

Si head es un IntNode, la función puede llamarse con head.getLink() (el caso recursivo) y puede ser solo esas mismas 2 entradas, y esto continúa hasta que head se convierta en null (el caso base).

---

Para responder a su pregunta real, sólo se devuelve el último valor del elemento debido a que en el caso recursivo, que está en realidad no anteponiendo el valor de la corriente IntNode (es decir,head.getData()); solo está devolviendo el resultado de la siguiente llamada reverse(), lo que significa que se repetirá hasta que llegue al último elemento, y devuelva solo valor de ese elemento.

Answer 2

Al pensar en la recursividad, es una buena estrategia para construir desde el suelo hasta llegar a casos interesantes. En cada paso, intente reutilizar casos anteriores.

Q1. ¿Cuál es el reverso de una lista vacía? []

A1. Una lista vacía []

---

Q2. ¿Cuál es el reverso de una lista con un solo elemento? [1]

A2. La misma lista. [1]

---

Q3. ¿Cuál es el reverso de una lista con dos elementos? [1 2]

A3. El primer elemento, agregado al segundo elemento. [2 1] (Comenzando a ser interesante)

---

Q4. ¿Cuál es el reverso de una lista con tres elementos? [1 2 3]

A4. El primer elemento, agregado al reverso de la lista de los elementos restantes. [3 2] + [1] = [3 2 1]

---

Ahora el patrón debe comenzar a ser claro: el reverso de una lista de N elementos es el reverso de la última N - 1 elementos con el primer elemento agregado).

¿Cuál es nuestro caso base? De lo anterior, parece tener una lista de 1 o 0 elementos. Sin embargo, mire más de cerca, aplicando nuestro patrón a una lista de longitud 1, vemos que [1] invertido es [] con el primer elemento agregado, es decir [] + [1]. Entonces, realmente, nuestro caso base es solo la lista vacía.

Answer 3

Como han señalado otros, su solución es más complicada de lo necesario.

En primer lugar, tenga en cuenta que no es necesario (y probablemente no quiere) eliminar los elementos de la lista para atravesarlo.

En segundo lugar, en lugar de verificar si el enlace del nodo actual es nulo, puedes verificar si el enlace actual es nulo (nada malo con eso, siempre y cuando no intentes desreferenciarlo). Esto simplifica la lógica.

public String reverse(IntNode head) { 
    if (head == null) 
     return ""; 
    else 
     return reverse(head.getLink()) + head.getData(); 
} 

O incluso se podría escribir así:

public String reverse(IntNode head) { 
    return (head == null)? "" : reverse(head.getLink()) + head.getData(); 
}