一、题目描述
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 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%的用户
