6. 从尾到头打印链表
6. 从尾到头打印链表
题目
输入一个链表的头节点,按链表从尾到头的顺序返回每个节点的值(用数组返回)。
Example:
输入:head = [3,6,4,1]
输出:[1,4,6,3]
Constraints:
0 <= 链表长度 <= 10000
解题思路
思路一:栈
可以借助「栈」这种先进后出的结构来得到链表的倒序遍历结果
思路二:递归
倒序打印一条单链表上所有节点的值,本质上就是后续遍历二叉树。递归函数本质上就是让操作系统帮我们维护了递归栈,和栈的解法效率上完全相同,但是这样写代码有助于我们深入理解递归的思维。
代码
栈
/**
* @param {ListNode} head
* @return {number[]}
*/
var reverseBookList = function (head) {
if (!head) return [];
let stack = [];
while (head) {
stack.push(head.val);
head = head.next;
}
return stack.reverse();
};
递归
/**
* @param {ListNode} head
* @return {number[]}
*/
var reverseBookList = function (head) {
if (!head) return [];
let stack = [];
let res = reverseBookList(head.next);
res.push(head.val);
return res;
};