Revert simplement chaînée liste inplace itérative

Question

Je suis d'apprentissage pour un examen à venir et nous avons l'exercice suivant:

Revert une liste simplement liée par les règles suivantes:

• itératives
• iNPLACE
• pas Constructors
• dernier élément a toujours null comme élément suivant

Je l'ai déjà trouvé quelques solutions et je suis venu avec mon propre:

public ListElement<T> revert(ListElement<T> head) 
{ 
    if(head == null) 
    return null; 

    ListElement<T> prev = null; 
    for(ListElement<T> next = head.next(); head.hasNext(); head = next){ 
     head.setNext(prev); 
     prev = head; 
    } 

    return head; 
} 

mais notre framework de test (donne seulement la rétroaction JUnit) ne me donne pas plus d'informations que ceci:

Testheadder – testReverseStatic_correct_inplace(singly_linked_list.reverse.test_reverse_iterative.TestReverseList) 

Message – test timed out after 30 milliseconds 

Qu'ai-je fait de mal?

Merci d'avance!

Answer 1

Dans votre mise en œuvre, la valeur de next ne change jamais:

ListElement<T> prev = null; 
for(ListElement<T> next = head.next(); head.hasNext(); head = next){ 
    head.setNext(prev); 
    prev = head; 
} 

Il est une compétence de programmeur souhaitable de pouvoir déboguer ces problèmes simples sur le papier. Il est important de pratiquer ceci. Vous pouvez écrire une table avec les variables et leurs changements d'état avec toutes les instructions, par exemple, compte tenu de l'état initial d'une liste chaînée de 1 -> 2 -> 3 -> null:

head = 1 -> 2 -> 3 -> null 
prev = null 

Les variables passent par les états suivants avec chaque instruction:

step    | prev   | head    | next 
start    | null   | 1 -> 2 -> 3 -> null | null 
next = head.next() | null   | 1 -> 2 -> 3 -> null | 2 -> 3 -> null 
head.setNext(prev) | null   | 1 -> null   | 2 -> 3 -> null 
prev = head  | 1 -> null  | 1 -> null   | 2 -> 3 -> null 
head = next  | 1 -> null  | 2 -> 3 -> null  | 2 -> 3 -> null 
head.hasNext() => true 
head.setNext(prev) | 1 -> null  | 2 -> 1 -> null  | 2 -> 1 -> null 
prev = head  | 2 -> 1 -> null | 2 -> 1 -> null  | 2 -> 1 -> null 
head = next  | 2 -> 1 -> null | 2 -> 1 -> null  | 2 -> 1 -> null 
head.hasNext() => true 
head.setNext(prev) | 2 -> 2 -> ... | 2 -> 2 -> ...  | 2 -> 2 -> ... 
prev = head  | 2 -> 2 -> ... | 2 -> 2 -> ...  | 2 -> 2 -> ... 
head = next  | 2 -> 2 -> ... | 2 -> 2 -> ...  | 2 -> 2 -> ... 
head.hasNext() => true 
... 

Par 2 -> 2 -> ... Je veux dire que 2 points à 2 lui-même, un cycle sans fin. Une fois ce cycle atteint, nous avons une boucle infinie. Tout est parce que next ne change jamais, et donc l'implémentation cesse de progresser.

est ici une solution possible:

public ListElement<T> reverse(ListElement<T> head) { 
    ListElement<T> prev = null; 
    for (ListElement<T> node = head; node != null;) { 
    ListElement<T> next = node.next(); 
    node.setNext(prev); 
    prev = head = node; 
    node = next; 
    } 

    return head; 
}