Inversion récursive d'une liste chaînée en Java

Question

Je travaille sur un projet en Java pour une classe pour un certain temps maintenant. C'est une implémentation d'une liste chaînée ( AddressList, contenant des nœuds simples appelés ListNode). Le hic, c'est que tout devrait être fait avec des algorithmes récursifs. J'étais capable de tout faire amende sans une méthode: public AddressList reverse()

ListNode:

public class ListNode{
  public String data;
  public ListNode next;
}

Droit maintenant, mon reverse fonction appelle une fonction d'assistance qui prend un argument pour permettre à la récursivité.

public AddressList reverse(){
  return new AddressList(this.reverse(this.head));
}

avec mon aide func avoir la signature d' private ListNode reverse(ListNode current)

Pour le moment, je l'ai à travailler de manière itérative à l'aide d'une pile, mais ce n'est pas ce que le cahier des charges exige. J'avais trouvé un algorithme en c que de manière récursive inversée et l'a converti en code Java à la main et il a travaillé, mais n'avait pas de compréhension.

edit: Nevermind, j'ai tout compris dans l'intervalle.

private AddressList reverse(ListNode current, AddressList reversedList){
  if(current == null) return reversedList;
  reversedList.addToFront(current.getData());
  return this.reverse(current.getNext(), reversedList);
}

Pendant que je suis ici, personne ne voir aucun problème avec cette route?

Answer 1

Il y a du code dans une réponse qui le précise, mais vous trouverez peut-être plus facile de commencer par le bas, en posant et en répondant à de petites questions (c'est l'approche dans The Little Lisper):

1. Quel est le contraire de null (la liste vide)? nul.
2. Quel est l'inverse d'une liste d'un élément? l'élément.
3. Quel est le contraire d'une liste d'éléments n? l'inverse du deuxième élément sur suivi du premier élément.

---

 public ListNode Reverse(ListNode list)
{
    if (list == null) return null; // first question

    if (list.next == null) return list; // second question

    // third question - in Lisp this is easy, but we don't have cons
    // so we grab the second element (which will be the last after we reverse it)

    ListNode secondElem = list.next;

    // bug fix - need to unlink list from the rest or you will get a cycle
    list.next = null;

    // then we reverse everything from the second element on
    ListNode reverseRest = Reverse(secondElem);

    // then we join the two lists
    secondElem.Next = list;

    return reverseRest;
}
 

Answer 2

Cette question m’a été posée lors d’un entretien et j’ai été contrariée de l’avoir tâtonnée car j’étais un peu nerveuse.

Cela devrait inverser une liste liée, appelée avec reverse (head, NULL); alors si c'était votre liste:

 1-> 2-> 3-> 4-> 5-> null
il deviendrait:
5-> 4-> 3-> 2-> 1-> null 

 
    //Takes as parameters a node in a linked list, and p, the previous node in that list
    //returns the head of the new list
    Node reverse(Node n,Node p){   
        if(n==null) return null;
        if(n.next==null){ //if this is the end of the list, then this is the new head
            n.next=p;
            return n;
        }
        Node r=reverse(n.next,n);  //call reverse for the next node, 
                                      //using yourself as the previous node
        n.next=p;                     //Set your next node to be the previous node 
        return r;                     //Return the head of the new list
    }
     

edit: ive fait comme 6 modifications sur cela, montrant que c'est toujours un peu difficile pour moi lol

Answer 3

Voici encore une autre solution récursive. Il contient moins de code dans la fonction récursive que certains autres, de sorte qu'il peut être un peu plus rapide. C'est C # mais je crois que Java serait très similaire.

 class Node<T>
{
    Node<T> next;
    public T data;
}

class LinkedList<T>
{
    Node<T> head = null;

    public void Reverse()
    {
        if (head != null)
            head = RecursiveReverse(null, head);
    }

    private Node<T> RecursiveReverse(Node<T> prev, Node<T> curr)
    {
        Node<T> next = curr.next;
        curr.next = prev;
        return (next == null) ? curr : RecursiveReverse(curr, next);
    }
}
 

Answer 4

L'algo devra travailler sur le modèle suivant,

• garder une trace de la tête
• Recurse jusqu'à la fin de la liste de liens
• Lien inverse

Structure:

 Head    
|    
1-->2-->3-->4-->N-->null

null-->1-->2-->3-->4-->N<--null

null-->1-->2-->3-->4<--N<--null

null-->1-->2-->3<--4<--N<--null

null-->1-->2<--3<--4<--N<--null

null-->1<--2<--3<--4<--N<--null

null<--1<--2<--3<--4<--N
                       |
                       Head
 

Code:

 public ListNode reverse(ListNode toBeNextNode, ListNode currentNode)
{               
        ListNode currentHead = currentNode; // keep track of the head

        if ((currentNode==null ||currentNode.next==null )&& toBeNextNode ==null)return currentHead; // ignore for size 0 & 1

        if (currentNode.next!=null)currentHead = reverse(currentNode, currentNode.next); // travarse till end recursively

        currentNode.next = toBeNextNode; // reverse link

        return currentHead;
}
 

Sortie:

 head-->12345

head-->54321