递归链表为什么最后返回rev的理解

首页课程实战体系课手记专栏慕课教程

递归链表为什么最后返回rev的理解

来源：3-3 翻转链表的递归实现

星火燎猿

2021-03-11 09:42:28

问题描述：

递归链表为什么最后返回rev的理解

相关截图：

相关代码：

//递归实现
public static ListNode reverseList2(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode rev = reverseList2(head.next);
    head.next.next = head;
    head.next = null;
    return rev;
}

可能有些人不理解为什么最后返回的是rev，参考leetcode上的一个动图，递归最后一层返回的是待反转链表的最后一个节点，也就是反转后链表的头节点，在递归的过程中这个头节点rev是不会变的，递归的过程只是从后往前处理链表的指针

head.next.next = head;
head.next = null;

处理指针的过程中，rev作为头节点，之后的节点指针指向会跟着变化。

其实这也是链表的基础概念，每个节点保存当前节点及下一个节点的引用。

写回答

1回答

liuyubobobo

2021-03-11

赞！感谢分享：）

继续加油！：）

hiuyubobobo

h04_

hp>你可以以一个具体的链表为例，比如 1->2->3，如果你认为 rev 是变的，那么，在函数内部，你认为 rev 到底变成了谁？（不用看地址，你给每一个节点附上不同的值，用节点的值就能讨论，这样更方便。）然后你可再进行一次跟踪，注意跟踪的目的是：你认为在具体代码的哪里，rev 会发生改变，具体从谁变成了谁？但实际上，在你认为 rev 会改变的地方，为什么没有发生改变？（如果你认为 3 个节点都太多，可以用两个节点的链表。）

h023-06-26

共2条回复

算法与数据结构

波波老师5年集大成之作，算法与数据结构系统学习，考试、面试、竞赛通用

2638 学习 · 1091 问题

查看课程

相似问题

反转链表的递归写法，最终的返回值是为什么会是rev，不太理解

回答 1

递归的时间和空间复杂度

回答 1

关于链表添加元素的递归算法返回值问题

回答 1

关于删除的递归操作

回答 1

dummyHead.next不是head吗，请老师解答一下

回答 1

打开慕课网App查看更多内容