firstLast Java Lié liste/nœuds

Question

Je suis confus sur la façon dont chaque nœud est relié à un autre et comment faire en sorte que si je veux que le premier nœud soit lié après celui à la fin, je ne suis pas un boucle infinie. Par exemple, dans ce problème ..

Ecrivez une méthode firstLast qui pourrait être ajoutée à la classe LinkedIntList qui déplace le premier élément de la liste vers l'extrémité arrière de la liste. Supposons qu'une liste nommée LinkedIntList stocke les éléments suivants de l'avant (gauche) à l'arrière (droite):

[18, 4, 27, 9, 54, 5, 63] Si vous avez fait l'appel de list.firstLast() ;, la liste stockera ensuite les éléments dans cet ordre:

[4, 27, 9, 54, 5, 63, 18] Si la liste est vide ou contient un seul élément, son contenu ne doit pas être modifié.

Ma première tentative est de faire this..but en vain:

`public void firstLast(){ 
    ListNode temp = front;//stores/references the first node 
    temp.next = null;//ensures that first node isn't referring to any other 
//node 
    ListNode current = front;//reaches end node/first one with a null 
//reference 
    while(current.next != null){ 
     current = current.next; 
    } 
    front.next = temp;//links end node to first node 
    front = current.next;////now that skips the first element` 

mais la sortie est [18] -> [18] (cycles!). S'il vous plaît conseiller

Answer 1

Je suis confus sur la façon dont chaque nœud se lié à un autre

Dans une liste unique liée, chaque nœud ne connaît que la suivante. Donc, vous devez garder une trace de la première, communément appelé head (dans votre mise en œuvre, il est "avant"), car il est essentiel d'accéder à tous les éléments.

... et comment vous assurer que si je veux que le premier nœud soit lié après celui à la fin, je ne suis pas en train d'exécuter une boucle infinie.

Le dernier nœud n'a pas le noeud suivant après, il est donc pointeur next est null. Vous pouvez utiliser cette condition pour éviter les boucles infinies. (Assurez-vous que le dernier noeud a next correctement comme null.)

Votre mise en œuvre pourrait être fixé comme:

public void firstLast() { 
    // list is empty or has single element -> nothing to do 
    if (front == null || front.next == null) { 
     return; 
    } 

    // save the first 
    ListNode first = front; 

    // move the head 
    front = front.next; 

    // find the end 
    ListNode current = front; 
    while (current.next != null) { 
     current = current.next; 
    } 

    // append the node 
    current.next = first; 

    // reset the next pointer of the new last node 
    first.next = null; 
} 

Answer 2

La fonction FirstLast() peut être codifiés comme suit:

public void firstLast() 
{ 
    ListNode temp = removeFirst(); 
    appendLast(temp); 
} 

Donc, maintenant vous avez cassé le problème en deux petits problèmes. Cela tend à être une très bonne stratégie pour résoudre n'importe quel type de problème. Le point dont vous devez vous rappeler, pour implémenter votre removeFirst(), est que vous devez modifier front pour pointer vers le 2ème nœud, qui est front.next.

Answer 3

Étant donné que vous mis en œuvre:

void push(ListItem item) { 
    end.next = item; 
    item.next = null; 
} 

et

ListItem pop() { 
    ListItem first = front; 
    front = front.next; 
    return first; 
} 

votre méthode devient:

void firstLast() { 
    push(pop()); 
} 

Remarque: code non testé sans contrôle pour null s ou liste Taille.