从头节点开始反转链表？

10 浏览
0 Comments

从头节点开始反转链表？

在网络上我看到了一个从尾部开始反转的程序，如下所示：

这里的node是头节点

reverseNode(int node){
    if(node==null){
        return;
    }
    reverseNode(node.next);
    Node temp = node.next;
    node.next = node.prev;
    node.prev=temp;
    if(node.prev==null){
        headNode = node;
    }
}

但是我可以想到一种从头部节点开始反转的方法

这里的node是头节点

reverseNode(int node){
    if(node==null){
        return;
    }
    Node temp = node.next;
    node.next = node.prev;
    node.prev=temp;
    reverseNode(node.prev);
   if(node.prev==null){
       headNode = node;
   }
}

但是我没有在任何地方看到这种方法。这种方法是否存在错误/问题或者是否不够优化？

0

1 答案

0 Comments

问题的出现原因：在讨论中提到了两种递归方式，即头递归（head recursion）和尾递归（tail recursion）。其中，尾递归的方法在反转链表的上下文中是有效的，并且在空间效率方面通常比头递归更高效，因为它更像一个循环（在递归步骤之前完成大部分工作，因此在调用栈上弹出的状态较少）。

问题的解决方法：尾递归方法是解决反转链表问题的有效方法。在Java中，虽然没有对尾递归进行优化，但在其他支持此功能的语言中，尾递归可以提供更好的性能。如果开始在Java中编写尾递归代码，一旦Java支持尾递归，代码将得到改进，同时还可以为已经支持尾递归的其他语言做好准备（这涉及到学习经验，而不是代码转换）。

文章整理如下：

反转链表从头节点开始（Reverse linked list from header node?）

第一个版本是头递归的一个示例。第二个版本是尾递归的一个示例。关于这两者的区别有很好的解释：The difference between head & tail recursion。

所以我的第二种方法在反转链表的上下文中是有效的。

是的，你的方法是有效的，并且通常在空间上比头递归更高效，因为它更像一个循环（在递归步骤之前完成大部分工作，因此在调用栈上弹出的状态较少）。

相关：stackoverflow.com/questions/33923

只是Java没有将尾递归实现为循环，因此头递归与尾递归之间没有区别。请参见Why doesn't Java have optimization for tail-recursion at all?

确实，在Java中没有区别，因为Java不支持尾递归。然而，在其他支持此功能的语言中，这可能会有所不同。

同意，并且由于链接的答案说Java最终会支持尾递归，如果现在开始编写代码，一旦Java支持尾递归，代码将得到改进，并且还可以准备好转到其他已经支持尾递归的语言（这涉及到学习经验，而不是代码转换，尽管代码转换也是）。

文章整理完毕。

0