Créer une liste chaînée miroir en Java

Question

Linked-List: Miroir

Considérez la classe privée suivante pour un nœud d'une liste simplement chaînée d'entiers:

private class Node{ 
public int value; 
public Node next; 
} 

Un wrapper de classe, appelée, ListImpl, contient un pointeur, appelé start au premier noeud d'une liste chaînée de Noeud .

Ecrire une instance méthode pour ListImpl avec la signature:

public void mirror(); 

Cela fait une copie inversée de la liste chaînée pointée par début et qui copient ajouter ses à la fin de la liste. Ainsi, par exemple la liste:

début 1 2 3

après un appel à miroir, devient:

début 1 2 3 3 2 1

Remarque: dans votre réponse que vous ne faites pas besoin de dene le reste de la classe pour ListImpl juste la méthode miroir.

Answer 1

Quelle est votre question? Cela ressemble à un problème d'exercice. Êtes-vous à la recherche d'une solution optimisée? Une façon serait d'itérer juste au-dessus de la liste et d'ajouter des éléments à une pile pour finalement les ajouter en tant que nœuds après l'itération.

Answer 2

Vous pouvez utiliser cette approche:

Algorithm findLinkedListMirror 
    If list does not exist 
    return 

    Let start and end be pointers to type Node 
    Position start to the first node of the list 
    Position end to last node of the list 

    While(start != end.next) 
    Add a new node next to end with value start.data 
    start = start.next 
    End While 

End 

Answer 3

public void mirror() { 
    if (start != null) { 
     Node prev = null; 
     Node p = start; 
     Node q = null; 
     while (p != null) { 
      Node n = new Node(); 
      n.value = p.value; 
      n.next = q; 
      q = n; 
      prev = p; 
      p = p.next; 
     } 
     prev.next = q; 
    } 
} 

Answer 4

Depuis Maurice a fourni un looping solution, je fournirai une solution récursive.

void mirror() 
{ 
    if (start == null) return; 
    mirrorSublist(start); 
} 

// returns the last node of the mirrored sublist 
Node mirrorSublist(Node firstOfSublist) 
{ 
    Node lastOfSublist = new Node(); 
    lastOfSublist.value = firstOfSublist.value; 
    lastOfSublist.next = null; 
    if (firstOfSublist.next == null) 
    { 
     firstOfSublist.next = lastOfSublist; 
    } 
    else 
    { 
     Node secondToLastOfSublist = mirrorSublist(firstOfSublist.next); 
     secondToLastOfSublist.next = lastOfSublist; 
    } 
    return lastOfSublist; 
}