输入一个链表按链表从尾到头嘚顺序返回一个ArrayList。
本题的递归方法会让你对递归有更深的理解
- 思路一:暴力顺序遍历一遍存储到临时集合templist中在定义一个集合逆序遍历存儲到list(不推荐)
-
listNode 是链表,只能从头遍历到尾但是输出却要求从尾到头,这是典型的"先进后出"可以想到栈!
当往list中添加元素是,如果都添加到0位置那么先添加到0位置的元素会被后来添加进来的元素往后挤,最后进来的元素会在0位置
而第一个到0位置的元素会被挤到末尾位置。这样返回的list是之前链表的逆序了listNode 即可得到逆序链表
-
listNode 是链表,只能从头遍历到尾但是输出却要求从尾到头,这是典型的"先进后出"可以想到栈!
先入栈,再用以一个链表接收弹栈值
-
递归法(不推荐不过该题让我对递归有了更深的理解)
理解:要实现单链表的输出,那么就须要遍历遍历的顺序是从头到尾。而节点输出的顺序是从尾到头
因此,先遍历到的节点后输出这是一个典型的 “后进先出”。要实现这种输出能够使用栈或递归。
通过这道题让我对 “递归在本质上就是一个栈结构” 理解的更加深刻
递归方法:递归的打印當前节点的下一个节点,但是这种方法当链表太多的时候调用深度过深,速度很慢
堆栈方法:遍历一个节点加入堆栈,遍历完成出栈利用了栈的先进后出的数据结构思想