图解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]为例，演示一下倒序输出的处理过程，请见下图所示：

四、代码实现

classSolution {
publicint[] result;
publicintindex=0, size=0;
publicint[] reversePrint(ListNodehead) {
build(head);
returnresult;
    }
publicvoidbuild(ListNodenode) {
if (node==null) {
result=newint[size]; // 在链表的最后一个节点处执行初始化数组result的操作return;
        }
size++; // 记录当前链表节点个数build(node.next); // 遍历下一个节点result[index++] =node.val; // 构建result数组中的元素    }
}
/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/

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

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

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