Loading [MathJax]/extensions/MathEvents.js

剑指 Offer 06. 从尾到头打印链表【递归、遍历、辅助栈】

题目描述

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

示例 1:

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

限制:

0 <= 链表长度 <= 10000

解题思路

方法一:递归

用递归的方法将链表的值存储到ArrayList数组中,进而将ArrayList数组赋值给res结果数组。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
public int[] reversePrint(ListNode head) {
ArrayList<Integer> tmp = new ArrayList<Integer>();
recur(head,tmp);
int[] res = new int[tmp.size()];
for(int i = 0; i < res.length; i++)
res[i] = tmp.get(i);
return res;
}
void recur(ListNode head,ArrayList<Integer> tmp) {
if(head == null) return;
recur(head.next,tmp);
tmp.add(head.val);
}

复杂度分析

时间复杂度:O(n)

空间复杂度:O(n)

方法二:两次遍历

先遍历一遍整个链表,计算出链表的长度。声明链表长度的数组res,再一次遍历链表,将链表值逆序存储到数组中。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int[] reversePrint2(ListNode head) {
if(head==null){
return new int [0];
}
int len=0;
ListNode premmyHead=head;
while (premmyHead!=null){
len++;
premmyHead=premmyHead.next;
}
int []res=new int[len];
int i=1;
premmyHead=head;
while(premmyHead!=null){
res[len-i]=premmyHead.val;
i++;
premmyHead=premmyHead.next;
}
return res;
}

复杂度分析

时间复杂度:O(n)

空间复杂度:O(n)

方法三:辅助栈

遍历整个链表将值插入到栈中,遍历完链表后,将栈中元素出栈顺序存储到结果数组res中。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
public int[] reversePrint3(ListNode head) {
Stack<Integer> stack =new Stack<>();
while(head!=null){
stack.push(head.val);
head=head.next;
}
int []res=new int[stack.size()];
for(int i=0;i<res.length;i++){
res[i]=stack.pop();
}
return res;
}

复杂度分析

时间复杂度:O(n)

空间复杂度:O(n)

资源

https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof

https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/solution/mian-shi-ti-06-cong-wei-dao-tou-da-yin-lian-biao-d/

剑指 Offer 06. 从尾到头打印链表【递归、遍历、辅助栈】

http://example.com/2021/03/28/06 从尾到头打印链表/

Author

John Doe

Posted on

2021-03-28

Updated on

2021-06-08

Licensed under

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.