11、剑指 Offer 06. 从尾到头打印链表
目录
一、题目
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
限制：
0 <= 链表长度 <= 10000
二、解法
2.1、辅助栈
核心思想：
栈的特点是后进先出，即最后压入栈的元素最先弹出。考虑到栈的这一特点，使用栈将链表元素顺序倒置。从链表的头节点开始，依次将每个节点的值压入栈内，然后依次弹出栈内的元素并存储到数组中。
复杂度分析：
时间复杂度：O(n)。正向遍历一遍链表，然后从栈弹出全部节点，等于又反向遍历一遍链表。
空间复杂度：O(n)。额外使用一个栈存储链表中的每个节点。
代码：
class Solution {
public int[] reversePrint(ListNode head) {
Stack<Integer> stack = new Stack<>();
// 遍历链表, 入栈
while (head != null) {
stack.push(head.val);
head = head.next;
}
int[] result = new int[stack.size()];
// 循环出栈,构造数据
for (int i = 0; i < result.length; i++) {
result[i] = stack.pop();
}
return result;
}
}
2.1、递归法
核心思想：
利用递归： 先走至链表末端，回溯时依次将节点值加入列表 ，这样就可以实现链表值的倒序输出。
- 递推阶段： 每次传入
head.next，以head == null（即走过链表尾部节点）为递归终止条件，此时直接返回。 - 回溯阶段： 层层回溯时，将当前节点值加入列表，即
tmp.add(head.val)。 - 最终，将列表
tmp转化为数组res，并返回即可。
复杂度分析：
时间复杂度：O(N)，遍历链表，递归 N 次。
空间复杂度：O(N)， 系统递归需要使用 O(N) 的栈空间。
代码：
class Solution {
ArrayList<Integer> arrayList = new ArrayList<>();
public int[] reversePrint(ListNode head) {
// 边界值
if (head == null) {
return new int[]{};
}
reverse(head);
int[] result = new int[arrayList.size()];
for (int i = 0; i < arrayList.size(); i++) {
result[i] = arrayList.get(i);
}
return result;
}
// 在递归遍历链表的回溯过程中利用 ArrayList 记录数据, 天然就是逆序的
public void reverse(ListNode node) {
if (node.next == null) {
arrayList.add(node.val);
return;
}
// 递归调用
reverse(node.next);
// 回溯阶段
arrayList.add(node.val);
}
}