剑指Offer_#6_从尾到头打印链表
Contents
题目
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]限制：
0 <= 链表长度 <= 10000
思路分析
方法1：辅助栈
遍历链表只能从头到尾，而这里需要我们从尾到头打印链表的节点，这可以借助栈的"先进后出"特点来实现。按照正序将各个节点的值入栈，出栈的时候就是倒序的。
方法2：递归
算法流程
先遍历到链表尾部，然后在回溯的过程中把值添加到结果数组中。
- 终止条件：
head == null,即遍历到链表的尾部 - 递推过程：
recur(head.next) - 回溯过程：
list.add(head)
在递归过程中，暂存结果的变量list可以写成一个类全局变量，也可以写成一个递归函数的参数，详见代码。
解答
解答1：辅助栈
class Solution {
public int[] reversePrint(ListNode head) {
Stack<Integer> stack = new Stack<>();
while(head != null){
stack.add(head.val);
head = head.next;
}
int[] res = new int[stack.size()];
for(int i = 0;i <= res.length - 1;i++){
res[i] = stack.pop();
}
return res;
}
}复杂度分析
时间复杂度：O(n)
空间复杂度：O(n)
解答2：递归
list做全局变量
class Solution {
List<Integer> list = new ArrayList<>();
public int[] reversePrint(ListNode head) {
//调用递归函数
recur(head);
//将结果转换为int数组
int[] res = new int[list.size()];
for(int i = 0;i <= res.length - 1;i++){
res[i] = list.get(i);
}
return res;
}
private void recur(ListNode head){
//终止条件：已经遍历到链表最尾端
if(head == null) return;
//递归调用开始，程序在此被阻塞住，直到满足终止条件，开始回溯
recur(head.next);
//回溯
list.add(head.val);
}
}list做递归方法参数
class Solution {
public int[] reversePrint(ListNode head) {
List<Integer> list = new ArrayList<>();
//调用递归函数
recur(head, list);
//将结果转换为int数组
int[] res = new int[list.size()];
for(int i = 0;i <= res.length - 1;i++){
res[i] = list.get(i);
}
return res;
}
private void recur(ListNode head,List<Integer> aList){
//终止条件：已经遍历到链表最尾端
if(head == null) return;
//递归调用开始，程序在此被阻塞住，直到满足终止条件，开始回溯
recur(head.next,aList);
//回溯
aList.add(head.val);
}
}复杂度分析
时间复杂度：O(n),递归函数调用n次
空间复杂度：O(n),递归调用n次，占用O(n)的栈空间