从尾到头打印链表

题目描述

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

解题思路

学过数据结构的人看到这个题目，很容易想到“栈”，栈有“后进先出”的特点，最后一个进去第一个出来。

在这道题中，我们可以使用栈将链表元素顺序倒置。意思就是说可以从链表的头节点开始，依次将每个节点压入（push）栈内，然后依次弹出（pop）栈内的元素并存储到数组中。

好了，思路解决了！我们来说说怎么用，用“栈”的方式解决这道题，有两种用法，一种是直接用Java Stack 类，一种则是用LinkedList。

方法一（Stack 类）

栈（Stack 类）是Vector的一个子类，它实现了一个标准的后进先出的栈。

在这个方法中，我们可以：

1. 创建一个栈（Stack ），用于存储链表的节点
2. 创建一个指针，初始时指向链表的头节点
3. 当指针指向的元素非空时，重复下列操作：（1）将指针指向的节点压入栈内（push）（2）将指针移到当前节点的下一个节点
4. 获得栈的大小 size，创建一个数组 print，其大小为 size
5. 循环遍历，从栈内弹出一个节点，将该节点的值存到 print[i]
6. 遍历结束后，返回 print

复杂性分析

时间复杂度：O(n)。正向遍历一遍链表，然后从栈弹出全部节点，等于又反向遍历一遍链表。

空间复杂度：O(n)。额外使用一个栈存储链表中的每个节点。

代码

class Solution {
public int[] reversePrint(ListNode head) {
Stack<ListNode> stack = new Stack<ListNode>();//创建一个栈
ListNode temp = head;//创建一个指针
while (temp != null) {
stack.push(temp);//将指针指向的节点压入栈内
temp = temp.next;//移到下一个节点
}
int size = stack.size();//获得栈的大小
int[] print = new int[size];//创建一个数组
for (int i = 0; i < size; i++) {
print[i] = stack.pop().val;//从栈内弹出一个节点，将该节点的值存到 `print[i]`
}
return print;//返回 `print`
}
}

方法二（LinkedList）

LinkedList和ArrayList一样是集合List的实现类。在这里，LinkedList充当栈（Stack）的作用，add相当于push，removeLast移除最后一个节点，相当于pop的作用。

复杂度分析

时间复杂度 O(N)： 入栈和出栈共使用 O(N)时间。

空间复杂度 O(N)： 辅助栈 stack 和数组 res 共使用 O(N) 的额外空间。

代码

class Solution {
public int[] reversePrint(ListNode head) {
LinkedList<Integer> stack = new LinkedList<Integer>();//初始化LinkedList
while(head != null) {
stack.add(head.val);//将指针指向的节点压入栈内
head = head.next;//移到下一个节点
}
int[] res = new int[stack.size()];//创建一个数组并获得栈的大小
for(int i = 0; i < res.length; i++)
res[i] = stack.removeLast();//从栈内弹出一个节点，将该节点的值存到res[i]
return res;//返回res
}
}

最后

以上就是活泼机器猫为你收集整理的从尾到头打印链表(Stack 类、LinkedList)从尾到头打印链表的全部内容，希望文章能够帮你解决从尾到头打印链表(Stack 类、LinkedList)从尾到头打印链表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。