Comment dupliquer récursivement tous les éléments d'une liste liée en Java?

Question

Je dois écrire une fonction dupliquée qui duplique chaque élément d'une liste chaînée et renvoie une liste chaînée telle que si L = [2,3,4] alors dupliquer (L) = [2,2,3,3,4 , 4]. Je dois le faire de manière récursive. Je me rends compte que ci-dessous n'est pas la bonne solution, mais je suis confus. = (

public class MyList { 
    int value; 
    MyList next; 

    public static MyList duplicate(MyList L){ 
     if(L.next == null){ 
      L.next.value = L.value; 
      L.next.next = null; 
     } else { 
      MyList temp = L.next; 
      L.next.value = L.value; 
      L.next.next = temp; 
      duplicate(L.next); 
     } 
     return L; 
    } 
} 

Answer 1

Tout d'abord, vérifiez que L n'est pas une liste vide (null). Si elle contient une valeur, retourner une nouvelle liste qui a cette valeur répétée deux fois, puis en dupliquant le reste de la liste.

En donnant MyList un constructeur, cela est plus facile à lire.

public class MyList { 
    int value; 
    MyList next; 

    public MyList(int value, MyList next) { 
     this.value = value; 
     this.next = next; 
    } 

    public static MyList duplicate(MyList list) { 
     if (list == null) { 
      return null; 
     } else { 
      return new MyList(list.value, 
        new MyList(list.value, 
         duplicate(list.next))); 
     } 
    } 
} 

Answer 2

Vous actuellement ajoutez un élément puis appel à la récursion sur elle, se terminant à sans cesse ajouter des éléments.

Vous avez besoin soit à des éléments derrière votre récursion lors du traitement dans un sens avant ou après la récursion lors du traitement en arrière.

---

Créons une version en arrière. Nous marchons d'abord récursivement jusqu'à la fin de la liste, puis résolvons la récursion en arrière, en ajoutant les éléments après à chaque fois notre élément actuel.

public <E> void duplicateEntries(MyLinkedList<E> list) { 
    // Do nothing if list is empty 
    if (list.size() != 0) { 
     // Call the recursive method on the head node 
     duplicateEntriesHelper(list.head); 
    } 
} 

public <E> void duplicateEntriesHelper(Node<E> node) { 
    // Walk to the end of the list 
    if (node.next != null) { 
     duplicateEntriesHelper(node.next); 
    } 

    // Resolve recursion, duplicate current 
    // entry by inserting it after the current element 
    Node<E> duplicatedEntry = new Node<>(); 
    duplicatedEntry.data = node.data; 

    // Insert element after current node 
    duplicatedEntry.next = node.next; 
    node.next = duplicatedEntry; 
} 

---

Les classes I utilisées devrait ressembler à:

public class MyLinkedList<E> { 
    public Node<E> head = null; 

    @Override 
    public String toString() { 
     // Build something like "MyLinkedList[2, 3, 4]" 
     StringBuilder sb = new StringBuilder(); 
     sb.append("MyLinkedList["); 

     StringJoiner sj = new StringJoiner(","); 
     Node<E> node = head; 
     while (node != null) { 
      sj.add(node); 
      node = node.next; 
     } 
     sb.append(sj); 

     sb.append("]"); 
     return sb.toString(); 
    } 
} 

public class Node<E> { 
    public Node next = null; 
    public E data = null; 

    @Override 
    public String toString() { 
     return E; 
    } 
} 

Et voici la démonstration:

public static void main(String[] args) { 
    // Setup the list 
    MyLinkedList<Integer> list = new MyLinkedList<>(); 

    Node<Integer> first = new Node<>(); 
    first.data = 2; 
    Node<Integer> second = new Node<>(); 
    second.data = 3; 
    Node<Integer> third = new Node<>(); 
    third.data = 4; 

    list.head = data; 
    first.next = second; 
    second.next = third; 

    // Demonstrate the method 
    System.out.println("Before: " + list); 
    duplicateEntries(list); 
    System.out.println("After: " + list); 
} 

Bien sûr, vous pouvez ajouter des méthodes et des fonctionnalités supplémentaires pour les . Par exemple en utilisant certains constructeurs ou getter/setter méthodes.