题目描述
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）
示例 1：
限制：
0 <= 链表长度 <= 10000
解析
方式一：递归法
解题思路：递归到链表尾端，在回溯时存入数组。
算法实现：
- 变量：先创建一个result数组，用size变量记录当前数组的下标索引，node为当前链表结点。
- 递归结束条件：当链表结点为null，node==null。
- 结果：result即为逆序排列链表数值后的数组，根据size对数组做截断并返回即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
int[] result = new int[10000];
int size = 0;
public int[] reversePrint(ListNode head) {
recurGet(head);
return Arrays.copyOfRange(result,0,size);
}
public void recurGet(ListNode node){
if(node == null){
return;
}
recurGet(node.next);
result[size++] = node.val;
}
}
|
复杂度分析：
- 时间复杂度O(N)：遍历整个链表
- 空间复杂度：本解法创建了一个大小为链表长度最大值的数组，结果对其做截断处理，故空间大小即为链表长度最大值；也可以使用集合代替数组，则空间复杂度为O(N)
方法二：栈
解题思路：由于栈具有先进后出的特点，故可用来将链表倒置。
算法实现：创建一个栈，顺序遍历链表便依次将结点值push入栈。最后根据栈的大小创建数组result，遍历栈赋值给数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 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()];
int i = 0;
while(!stack.isEmpty()){
result[i++] = stack.pop();
}
return result;
}
}
|
复杂度分析：
- 时间复杂度O(N): 先遍历链表给栈赋值（入栈），再遍历栈给数组赋值（出栈）
- 空间复杂度O(N): 栈与数组的大小均与链表长度有关
方法三：使用两个数组模拟栈
解题思路：遍历链表给第1个数组赋值，再将第1个数组逆序赋值给第2个数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int[] reversePrint(ListNode head) {
int[] node = new int[10000];
int size = 0;
int i = 0;
while(head!=null){
node[size++] = head.val;
head = head.next;
}
int[] result = new int[size--];
while(size>=0){
result[i++] = node[size--];
}
return result;
}
}
|
