主题
06. 从尾到头打印链表
来源
https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
题目
输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。
示例:
输入:head = [1,3,2]
输出:[2,3,1]
限制:
0 <= 链表长度 <= 10000
思路
使用 js 数组的 unshift 方法,遍历链表,从顶部压入,实现起来很简单。
时间复杂度 O(n), 空间复杂度 O(n)。
解题
js
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {number[]}
*/
var reversePrint = function (head) {
const arr = [];
let cur = head;
while (cur) {
arr.unshift(cur.val);
cur = cur.next;
}
return arr;
};
思路 2
可以用栈解决的问题,同样也可以使用递归函数解决,只是要注意调用栈溢出问题。
时间复杂度 O(n), 空间复杂度 O(n)。
解题 2
js
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {number[]}
*/
var reversePrint = function (head) {
const arr = [];
const nextNode = (cur) => {
if (cur) {
if (cur.next) {
nextNode(cur.next);
}
arr.push(cur.val);
}
};
nextNode(head);
return arr;
};
递归经常用来实现洋葱结构,如redux、koa的中间件
从零开始学算法
https://github.com/daqi/re0-algorithm/issues
欢迎 start & watch