剑指 Offer 06. 从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例.png
思路一：反转链表，遍历反转后的链表把节点的值添加到数组中
时间复杂度: O(n) ,正向遍历一遍链表n是链表节点数
空间复杂度: O(1) 只是定义了几个变量
//反转链表 遍历反转后的链表把节点值添加到数组
class Solution {
public int[] reversePrint(ListNode head) {
//0.边界判断
if(head==null) return new int[]{};
//1.定义需要的数据结构
int length = 0;
//2.反转链表
ListNode prev = null;
ListNode curr = head;
while(curr != null) {
ListNode tmp = curr.next;
curr.next = prev;
prev = curr;
curr = tmp;
length++;
}
//2.1遍历反转后的链表 把val添加进数组
int[] res = new int[length];
int idx = 0;
while(prev != null) {
res[idx] = prev.val;
prev = prev.next;
idx++;
}
//3.返回结果
return res;
}
}
思路一提交结果.png
思路二：辅助栈 ，遍历链表入栈，遍历栈弹出节点 利用栈的先进后出原理
时间复杂度: O(n) ,正向遍历一遍链表 然后从栈中弹出全部节点，等于又反向遍历一遍链表
空间复杂度: O(n) 额外使用一个栈存储链表中的每一个节点
//遍历链表入栈，再遍历栈弹出节点
class Solution {
public int[] reversePrint(ListNode head) {
//0.边界判断
if(head==null) return new int[]{};
//1.定义需要的数据结构
//ArrayDeque是一个集合类,用Deque接收但仍然可以当栈来用 其性能比new Stack<Integer>()好
Deque<Integer> stack = new ArrayDeque<>();
int length = 0;
//2.遍历链表把节点值入栈
ListNode curr = head;
while(curr != null) {
stack.push(curr.val);
curr = curr.next;
length++;
}
//3.遍历栈弹出节点值
int[] res = new int[length];
int idx = 0;
while(!stack.isEmpty()) {
res[idx] = stack.pop();
idx++;
}
//4.返回结果
return res;
}
}
思路二提交结果.png
思路三：遍历链表计算出链表长度；创建数组 再次遍历链表 倒序给数组添加节点的值
时间复杂度: O(n) ,正向遍历一遍链表n是链表节点数
空间复杂度: O(1) 只是定义了几个变量
//遍历链表计算出链表长度，再次遍历链表倒序的把节点值添加到数组中
class Solution {
public int[] reversePrint(ListNode head) {
//0.边界判断
if(head==null) return new int[]{};
//1.定义需要的数据结构
int length = 0;
//2.遍历求出链表长度
ListNode curr = head;
while(curr != null) {
curr = curr.next;
length++;
}
curr = head;//重置
//3.倒叙把val添加到数组
int[] res = new int[length];
int idx = length - 1;
while(curr != null) {
res[idx] = curr.val;
curr = curr.next;
idx--;
}
//4.返回结果
return res;
}
}
思路三提交结果.png
