java - tda - La Lista enlazada no itera en el ciclo while correctamente cuando usa el siguiente método

tipos de datos abstractos en java

Question

Intento revertir una lista vinculada iterativamente usando una pila. He identificado dónde está ocurriendo el problema, pero durante toda la vida, no puedo entender por qué el código no se itera correctamente cuando llamo al siguiente método de ListNode. He marcado en el código a continuación, donde ocurre el error.

Este es el resultado cuando ejecuto el código:

Before: 1->2->3->4->null
After: 4->3->3->4->null

Este es el resultado que debería ser:

Before: 1->2->3->4->null
After: 4->3->2->1->null

¿Alguien puede indicarme la dirección correcta de lo que está pasando? ¡Gracias!

Aquí está el código:

public class Solution {
    public static void main(String[] args) {
        private static Solution soln = new Solution();
        ListNode head = makeLinkedList(4);

        System.out.print("Before: ");
        printLinkedList(head);
        System.out.println();

        soln.reverseList(head);

        System.out.print(" After: ");
        printLinkedList(head);

        System.exit(0);
    }

    public ListNode reverseList(ListNode head) {
        Stack<ListNode> listContents = new Stack<ListNode>();

        // iterate list and add to stack
        ListNode tmp = head;
        while (tmp != null) {
            listContents.push(tmp);
            tmp = tmp.next;
        }

        // iterate list again and replace each val with stack val
        tmp = head;
        while (tmp != null) {
            tmp.val = listContents.pop().val;
            // this is where the code seems to fail
            tmp = tmp.next; 
        }
        return head;
    }
}

Cómo se define ListNode:

public class ListNode {
    int val;
    ListNode next = null;

    public ListNode(int item) { 
        val = item; 
    }
}

Aquí es cómo creo una lista vinculada:

private static ListNode makeLinkedList(int numNodes) {
    ListNode head = null;
    ListNode tmp = null;
    for (int i = 1; i < numNodes + 1; i++) {
        if (tmp == null) {
            tmp = new ListNode(i);
            head = tmp;
        } else {
            tmp.next = new ListNode(i);
            tmp = tmp.next;
        }
    }
    return head;
}

Un método de ayuda:

private static void printLinkedList(ListNode head) {
    ListNode tmp = head;
    while (tmp != null) {
        System.out.print(tmp.val + "->");
        tmp = tmp.next;
    }
    System.out.print("null");
}

Answer 1

Por que no funciona?

El problema es que está almacenando ListNode s en la Stack lugar de solo los valores. De esta forma, sobrescribes los valores de los nodos que estás leyendo:

• Empiezas con pila (arriba primero): 4 - 3 - 2 - 1
• Tomas la cabeza anterior, la pila pop y escribes el valor
  • Nueva lista: 4
  • Sin embargo, Stack ahora es: 3 - 2 - 4 (sobrescribió el valor en la cabeza)
• Siguiente elemento
  • Nueva lista: 4 - 3
  • Pila: 3 - 4 (sobrescribió el valor en el segundo nodo de la lista)
• Siguiente elemento
  • Nueva lista: 4 - 3 - 3
  • Pila: 4
• Último elemento
  • Nueva lista: 4 - 3 - 3 - 4

¿Qué hacer para que funcione?

Varias formas posibles de solucionarlo:

• Solo almacena los valores en la pila.
• Crea nuevos ListNode para la lista invertida.
• Vuelva a conectar los nodos en lugar de reescribir sus valores. Tenga en cuenta que esto se puede hacer sin usar la Stack ; vea cómo en la respuesta de @xenteros.

Answer 2

Esto está sucediendo porque estás mutando tu LinkedList sin darte cuenta. En otras palabras, cuando sobreescribe el valor de más en su LinkedList, los nodos que ha insertado previamente en la pila también se modificarán. Por lo tanto, una forma de garantizar que esto no ocurra es crear instancias y empujar un nuevo nodo (copia) en la pila:

public ListNode reverseList(ListNode head) {
 Stack<ListNode> listContents = new Stack<ListNode>();

 // iterate list and add to stack
 ListNode tmp = head;

 while (tmp != null) {
     ListNode newNode = new ListNode(temp);
     listContents.push(newNode);
     tmp = tmp.next;
 }

 // iterate list again and replace each val with stack val
 tmp = head;
 while (tmp != null) {
     tmp.val = listContents.pop().val;
     tmp = tmp.next; 
 }
 return head;
}

Modificación simple a la clase ListNode para agregar el constructor de copia:

public class ListNode {
  int val;
  ListNode next = null;

  public ListNode (ListNode that){
     this.val = that.val;
      this.next = null;     //Could be that.next
   }

  public ListNode(int item) { 
      val = item; 
  }
}

Answer 3

Invertir una lista vinculada debe hacerse invirtiendo enlaces si es posible. Intentaría lo siguiente:

public static ListNode reverseList(ListNode head) {
    // iterate list and add to stack
    ListNode current = head;
    ListNode previous = null;
    ListNode temp = null;
    while (current.next != null) {
        temp = previous;
        previous = current;
        current = current.next;
        previous.next = temp;
    }
    current.next = previous;
    return current;
}

Devuelve una nueva cabeza. Ejemplo de uso:

public static void main(String[] args) {

    ListNode head = makeLinkedList(4);

    System.out.print("Before: ");
    printLinkedList(head);
    System.out.println();

    head = reverseList(head);

    System.out.print(" After: ");
    printLinkedList(head);

    System.exit(0);
}

>>Before: 1->2->3->4->null
>>After: 4->3->2->1->null
>>Process finished with exit code 0

La descripción del algoritmo sería: para cada nodo en una lista, en lugar de vincular el elemento siguiente, vincule el anterior y devuelva el último elemento como encabezado.