使用递归反转双链表

Question

我正在编写程序来使用递归反转双链表。我知道如何迭代实施。但陷入了递归。

这是我所拥有的

public static Node reverseRecurseDoubleLinkedList(Node node){
        if (node==null || node.next==null)
            return node;
        Node newNode = reverseRecurseDoubleLinkedList(node.next);
        node.next.next=node;
        node.next=null;
        node.prev=newNode;
        return newNode;
    }

我发现prev指针设置不正确。但next指针实际上是正确的。

谢谢

Answer 1

一般来说，简化递归代码思考的一种方法是仅考虑递归调用完成时提供的保证。然后，您需要检查这些保证在停止递归的基本情况下是否成立（例如空列表或具有单个节点的列表），并且它们在每个附加递归调用中得到维护。

提供的代码存在一些问题：

• 停止递归的条件没有正确处理 时的情况node.next == null。在这种情况下，该node.prev字段应该设置为null。

• 变量名称newNode可能会引起一些混乱。它代表反向列表的新头（这是初始列表的尾部）。我将其重命名为newHead.

• 与上面的观点相关，分配node.prev=newNode;是不正确的——我们不希望prev每个节点的 指向新列表的头部。

合并这些方面后，下面的代码正确地反转了列表：

public static Node reverseRecurseDoubleLinkedList(Node node) {
    if (node == null) {
        return node;
    }

    if (node.next == null) {
        node.prev = null;
        return node;
    }

    Node newHead = reverseRecurseDoubleLinkedList(node.next);
    node.next.next = node;
    node.prev = node.next;
    node.next = null;

    return newHead;
}