Liste di collegamento ricorsive in Java

Question

Sto lavorando su un compito che mi ha scritto un programma java per stampare in ordine inverso i dati contenuti in un elenco collegato utilizzando la ricorsione. Finora questo è quello che ho, funziona, ma solo sull'ultimo elemento nell'elenco IE. si ferma una volta stampato l'ultimo 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()); 
     } 
    } 

Come si può ottenere che continui a scorrere l'elenco indietro nell'albero ricorsivo?

Answer 1

Questo codice è più complicato di quanto deve essere. In questo caso la ricorsione può essere suddiviso in 2 casi (o 2 percorsi di esecuzione la funzione potrebbe avere):

1. caso ricorsivo: questo percorso si chiama affinché ricorsione può iniziare (o continuare)
2. caso base: questo percorso termina la ricorsione restituendo senza che si fa chiamare

il codice ha 2 casi di base, e ha bisogno solo 1. Pensate a tutte le diverse ingressi è possibile chiamare la funzione con:

1. head è null

2. head è un IntNode:

   a. head.getLink() restituisce null

   b. head.getLink() restituisce una IntNode:

   1. head.getLink().getLink() rendimenti null

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

Inizierete a notare un modello; una volta che è semplificato ci sono solo 2 ingressi possibili:

1. head è null
2. head è un IntNode

Se head è un IntNode, la funzione può chiamarsi con head.getLink() (caso ricorsivo) e può essere solo gli stessi 2 ingressi e continua fino a head diventa null (il caso base).

---

Per rispondere alla tua domanda attuale, restituisce solo il valore dell'ultimo elemento perché nel caso ricorsivo, si sta in realtà non anteponendo il valore della corrente IntNode (vale a direhead.getData()); stai solo restituendo il risultato della prossima chiamata reverse(), il che significa che reciterà fino a raggiungere l'ultimo elemento e restituirà solo a il valore di quell'elemento.

Answer 2

Quando si pensa alla ricorsione, è una buona strategia per costruire da terra, fino a quando non si colgono casi interessanti. Ad ogni passo, prova a riutilizzare i casi precedenti.

Q1. Qual è il contrario di una lista vuota? []

A1. Una lista vuota. []

---

Q2. Qual è il contrario di una lista con un singolo elemento? [1]

A2. La stessa lista. [1]

---

Q3. Qual è il contrario di una lista con due elementi? [1 2]

A3. Il primo elemento, aggiunto al secondo elemento. [2 1] (Iniziare a interessarsi)

---

Q4. Qual è il contrario di una lista con tre elementi? [1 2 3]

A4. Il primo elemento, aggiunto al retro dell'elenco degli elementi rimanenti. [3 2] + [1] = [3 2 1]

---

Ora il modello dovrebbe iniziare a essere chiaro: l'opposto di una lista di N elementi è il contrario degli ultimi N - 1 elementi con il primo elemento aggiunto).

Qual è il nostro caso base? Da quanto sopra, sembra avere una lista di 1 o 0 elementi. Guardate più da vicino, applicando il nostro modello a un elenco di lunghezza 1, vediamo che [1] invertito è [] con il primo elemento aggiunto, cioè [] + [1]. Quindi, davvero, il nostro caso base è solo la lista vuota.

Answer 3

Come altri hanno sottolineato, la soluzione è più complicata di quanto non debba essere.

In primo luogo, si noti che non è necessario (e probabilmente non lo desidera a) rimuovere qualsiasi elemento dall'elenco per poterlo attraversare.

In secondo luogo, anziché controllare se il collegamento del nodo corrente è nullo, è possibile verificare effettivamente se il collegamento corrente è nullo (non c'è niente di male in questo finché non si tenta di dereferenziarlo). Questo semplifica la logica.

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

Oppure si potrebbe anche scrivere in questo modo:

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