|
目录
一、题目描述
二、思路讲解
三、算法描述
四、Java代码实现
五、时空复杂度分析
一、题目描述
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
限制：
0 <= 链表长度 <= 10000
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int[] reversePrint(ListNode head) {
}
}
二、思路讲解
? ? ? ? 要实现从尾到头输出，很容易想到使用栈的先进后出。
三、算法描述
? ? ? ? 将链表里的值一一压入栈中，再一一弹出，使用数组保存即可。
四、Java代码实现
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int[] reversePrint(ListNode head) {
Stack<ListNode> stack = new Stack<ListNode>();
int size = 0; //用以保存链表的长度
//将链表中的值一一压入栈中
while(head != null) {
stack.push(head);
size++;
head = head.next;
}
int []a = new int[size];
//将栈中的值逐一弹出，并用数组接收保存
for(int i=0; i<size; i++) {
a[i] = stack.pop().val;
}
return a;
}
}
五、时空复杂度分析
? ? ? ? 时间复杂度：O(n)? ? ? ? 正向遍历一遍链表，反向遍历一遍栈
? ? ? ? 空间复杂度：O(n)? ? ? ? 使用额外的一个栈保存数据
????????执行用时：1 ms, 在所有?Java?提交中击败了71.90%的用户
????????内存消耗：39 MB, 在所有?Java?提交中击败了57.02%的用户
|