通过更改连接从单链表转换为双链表

Question

我有一个 doubly linked list 可以模拟 singly linked list 的行为。所以我有左、右和信息，但左边始终为空。像这样：

1 -> 2 -> 3 -> 4

我想要的是在不重新创建节点的情况下将其改回 doubly，只需解析列表并重新建立连接。

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

我有

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

还有我的方法：

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

这是行不通的。它使我的程序抛出堆栈溢出，因为当我将 2 连接到 1 时，1 已经连接到 2-> 3 -> 4，因此它将开始一遍又一遍地复制那段列表，这不是我想要的。

有解决办法吗？

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 +
                '}';
    }

好的，经过更多调试，它似乎确实在 toDoublyLinked 中抛出了 Whosebug，但在 toString 方法中。为什么它甚至在该方法中调用 toString ？我不是。至少没有明确说明。我能理解为什么 toString 是错误的，但即使我评论它，它仍然无法正常工作。

Answer 1

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

如果要递归：

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

但请记住，正如我之前所说，由于 Java 没有尾递归优化，即使它在技术上和意识形态上都是正确的，也会在长列表上发生堆栈溢出；

Answer 2

您不应使用会导致长列表堆栈溢出的递归。您应该做的是使用迭代方法，例如：

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

这样，无论列表的长度如何，您的代码都不会导致堆栈溢出。当然你有一个额外的变量，但你会避免长列表的堆栈溢出并提高复杂性（调用函数成本更高）。

但是，如果您仍然只想使用递归（即使您不应该），这里有一段代码：

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

通过更改连接从单链表转换为双链表

Transforming from singly linked list to doubly by changing the connections

java

linked-list

doubly-linked-list