题解 | #从尾到头打印链表#
从尾到头打印链表
http://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035
算法思想一：辅助数组
解题思路：
1、创建存储链表结点元素的数组 res
2、遍历链表，并同时将遍历的结点存储入数组
3、倒序输出数组结果
图解:
链表：{1，2，3}
| 步骤 | 链表 | 数组 |
| 1 | 遍历结点 1 | 【1】 |
| 2 | 遍历结点 2 | 【1，2】 |
| 3 | 遍历结点 3 | 【1，2，3】 |
| 倒序输出数组：【3，2，1】 | ||
代码展示：
Python
class Solution: # 返回从尾部到头部的列表值序列，例如[1,2,3] def printListFromTailToHead(self, listNode): # write code here res = [] while listNode: # 遍历链表，存入数组中 res.append(listNode.val) listNode = listNode.next # 数组反向输出 return res[::-1]
复杂度分析：
时间复杂度O(N)：N是链表的长度，遍历这个链表花费时间
空间复杂度O(N)：额外存储结点数组空间
算法思想二：递归
解题思路：
递归到链表的尾部，再依次将链表结点存入数组中 算法实现：
变量：先创建一个list数组
递归结束条件：当链表结点为null，listNode==null。
结果：list即为逆序排列链表数值后的数组
变量：先创建一个list数组
递归结束条件：当链表结点为null，listNode==null。
结果：list即为逆序排列链表数值后的数组
图解：
代码展示：
JAVA版本
import java.util.ArrayList;
public class Solution {
ArrayList<Integer> list = new ArrayList();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode!=null){
// 递归到最后一个链表结点
printListFromTailToHead(listNode.next);
// 依次将链表结点元素存入列表
list.add(listNode.val);
}
return list;
}
} 复杂度分析：
时间复杂度O(N)：N是链表的长度，递归整个链表
空间复杂度O(N)：额外存储空间
算法思想三：栈
解题思路：
1、借助栈的先进后出机制，遍历链表的同时将遍历结点元素入栈 2、遍历结束依次将站内元素出栈
图解： 链表：{1，2，3}
| 步骤 | 链表 | 栈 | 返回数组 |
| 1 | 遍历结点 1 | 入栈【1】 | 【】 |
| 2 | 遍历结点 2 | 入栈【1，2】 | 【】 |
| 3 | 遍历结点 3 | 入栈【1，2，3】 | 【】 |
| 4 | | 3 出栈 | 【3】 |
| 5 | | 2 出栈 | 【3，2】 |
| 6 | | 1 出栈 | 【3，2，1】 |
代码展示：
Python版本
class Solution: # 返回从尾部到头部的列表值序列，例如[1,2,3] def printListFromTailToHead(self, listNode): # write code here if not listNode: return [] # 辅助栈 stack = [] res = [] while listNode: stack.append(listNode.val) # 进栈 listNode = listNode.next while stack: res.append(stack.pop()) # 出栈 return res
复杂度分析：
时间复杂度O(N)：N是链表的长度，遍历整个链表
空间复杂度O(N)：额外栈存储空间
查看17道真题和解析
