图解LeetCode——剑指 Offer 06. 从尾到头打印链

一、题目

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

二、示例

示例 1：

【输入】head = [1,3,2]
【输出】[2,3,1]

限制：

• 0 <= 链表长度 <= 10000

三、解题思路

根据题目描述我们可以得知要操作的数据结构是一条单向链表，它能向后遍历next节点，所以，如果我们想要从链表尾部开始构建数组result并输出的话，最简单的解题方式就是，如果链表有N个节点，我们就执行N次遍历，逐一的从尾向首去构建数组result。

但是，上面这种方式由于采取了重复遍历，所以时间繁杂度会很高。那么是否还有其他处理方式呢？我们其实可以采取回溯的方式，步骤如下：

【步骤1】判断当前节点是否是最后一个节点，如果是，则构建result数组。
【步骤2】利用递归方式，访问下一个节点。
【步骤3】将将当前节点的值保存到result数组中。

以上就是这道题的解题思路，下面我们以链表[1, 3, 2]为例，演示一下倒序输出的处理过程，请见下图所示：

四、代码实现

class Solution {
    public int[] result;
    public int index = 0, size = 0;
    public int[] reversePrint(ListNode head) {
        build(head);
        return result;
    }
    public void build(ListNode node) {
        if (node == null) {
            result = new int[size]; // 在链表的最后一个节点处执行初始化数组result的操作
            return;
        }
        size++; // 记录当前链表节点个数
        build(node.next); // 遍历下一个节点
        result[index++] = node.val; // 构建result数组中的元素
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o)/ ~ 「干货分享，每天更新」