Umwandlung von einfach verknüpften Liste zu doppelt durch Ändern der Verbindungen

Question

Ich habe eine doubly linked list, die das Verhalten einer singly linked list simuliert. Also habe ich links, rechts und Info, aber die linke ist immer null. Etwas wie folgt aus:

1 -> 2 -> 3 -> 4 

Was ich will, ist es in doppelt zurück zu wechseln, ohne die Knoten neu zu erstellen, indem Sie einfach die Liste Parsen und die Verbindungen remaking.

1 -> <- 2 -><- 3 -><- 4 

Ich habe

class Node { 
    private int info; 
    private Node left; 
    private Node right; 

Und meine Methode:

static Node toDoublyLinked(Node root) { 
     if (root.getRight() != null) { 
      root.getRight().setLeft(root); 
      return toDoublyLinked(root.getRight()); 
     } 
     return root; 
    } 

Welche funktioniert nicht. Es macht mein Programm, Stapelüberlauf zu werfen, weil, wenn ich 2 zu 1 verbinde, hat 1 bereits Verbindungen zu 2-> 3 -> 4, so wird es anfangen, das Stück der Liste immer wieder zu kopieren, was nicht was ich will.

Gibt es eine Lösung, um dies zu lösen?

void add(int info) { 
     Node s = new Node(); 
     if (this.info == 0) { 
      this.info = info; 
     } else { 
      if (info < this.info) { 
       if (left != null) { 
        left.add(info); 
       } else { 
        s.setInfo(info); 
        this.left = s; 
       } 
      } else { 
       if (right != null) { 
        right.add(info); 
       } else { 
        s.setInfo(info); 
        this.right = s; 
       } 
      } 
     } 
    } 

    public int getInfo() { 
     return info; 
    } 

    public void setInfo(int info) { 
     this.info = info; 
    } 

    public Node getLeft() { 
     return left; 
    } 

    public void setLeft(Node left) { 
     this.left = left; 
    } 

    public Node getRight() { 
     return right; 
    } 

    public void setRight(Node right) { 
     this.right = right; 
    } 

    @Override 
    public String toString() { 
     return "Node{" + 
       "info=" + info + 
       ", left=" + left + 
       ", right=" + right + 
       '}'; 
    } 

Ok nach etwas mehr Debugging, scheint es, dass es in der Stackoverflow toDoublyLinked wirft aber in der toString-Methode. Warum ruft es in dieser Methode sogar toString auf? Ich bin nicht. Nicht explizit zumindest. Ich kann verstehen, warum der toString falsch gemacht wird, aber selbst wenn ich es kommentiere, funktioniert es immer noch nicht richtig.

Answer 1

public static void toDoublyLinked(Node node) { 
    Node current = node; 
    while (current.getRight() != null) { 
     current.getRight().setLeft(current); 
     current = current.getRight(); 
    } 
} 

Wenn Sie Rekursion:

public static void toDoublyLinked(Node node) { 
    if (node.getRight() != null) { 
     node.getRight().setLeft(node); 
     toDoublyLinked(node.getRight()); 
    } 
} 

aber daran erinnern, wie ich schon sagte, da Java nicht Endrekursion Optimierung hat, diesen Überlauf auf langen Listen-Stack, obwohl es technisch und ideologisch korrekt;

Answer 2

Sie sollten keine Rekursion verwenden, die Stapelüberlauf über lange Listen verursacht. Was sollten Sie stattdessen tun, ist ein iteratives Verfahren verwendet werden, wie:

public static void toDoublyLinked(Node node){ 
    Node currentNode = node ; 
    while(currentNode.getRight() !=null){ 
     currentNode.getRight().setLeft(currentNode); 
     currentNode = currentNode.getRight(); 
      } 
} 

diese Weise wird Ihr Code nicht einen Stapelüberlauf unabhängig von der Länge der Liste führen. Sicher haben Sie eine zusätzliche Variable, aber Sie vermeiden den Stapelüberlauf mit langen Listen UND verbessern die Komplexität (das Aufrufen einer Funktion kostet mehr).

Wenn Sie jedoch nach wie vor nur wollen Rekursion verwenden (auch wenn Sie nicht tun sollten), hier ist ein Stück Code:

public static void toDoublyLinked(Node node) { 
    if (node.getRight() != null) { 
     node.getRight().setLeft(node); 
     toDoublyLinked(node.getRight()); 
    } 
}