剑指 Offer 6. 从尾到头打印链表

🟢   🔖  栈 递归 链表 双指针  🔗 LeetCode

题目

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

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;
};