我正在编写程序来使用递归反转双链表。 我知道如何迭代实现。但陷入了递归。
这是我的
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
指针实际上是正确的。
谢谢
最佳答案
一般来说,简化递归代码思考的一种方法是只考虑递归调用完成时提供的保证。然后,您需要检查这些保证是否适用于停止递归的基本情况(例如,空列表或具有单个节点的列表),并且它们是否在每次额外的递归调用中得到维护。
提供的代码中存在一些问题:
停止递归的条件没有正确处理
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;
}
关于java - 使用递归反向双链表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36539546/