【刷题第 13 天】剑指 Offer 06. 从尾到头打印链表

一、题目描述：

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

示例 1：

输入： head = [1,3,2]输出： [2,3,1]复制代码

二、思路分析：

这也是计算机数据结构与算法的经典题目，反向打印链表。提到反向打印，我们应该首先会想到栈。

栈是先进后出的特点，即后入的元素会在栈顶然后最先别弹出，因此我们可以利用这个特性，实现链表元素顺序反向。

算法流程大致是这样的:

• 创建一个空栈 stack ，存储链表的元素

• 创建指向链表头节点的指针

• 遍历链表，当链表非空时: 将当前指针存放的元素压入栈中，然后指针后移，不断进行此流程

• 遍历链表完毕后，获取栈的大小 length

• 建立 result 数组，数组大小为 length，存储链表节点值

• 当栈非空时，弹出栈顶元素，将栈顶元素的值存放到 result 数组中

• 重复上述流程，直至栈元素全部被弹出

• 然后返回 result 数组即可。

上面时大体的实现思路，我们可以将上面的过程融合在一部中实现。

特殊实现

上面我们使用的是栈做数据结构，但是其实 JavaScript 提供了很方便数组方法，即 unshift 方法，unshift 方法支持在数组头部插入元素。因此我们可以边遍历链表的时候，不断在数组头部插入元素，这样就模仿了栈的实现，而且大量简略了时间，只需遍历链表一次。

三、AC 代码：

// var reversePrint = function (head) {    let nums = []    let node = head    //遍历链表    while(node !== null) {        nums.unshift(node.val)        node = node.next    }    return nums}复制代码

四、总结：

其实做完这个题目后，我反应过来这个题目同时还是有递归方法的，但我还是没有想出递归方法，递归真是世界难题，裂开。