Offer06（从尾到头打印链表）

发表于 | 分类于 ，

题目：

　　输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

思路：

　　倒序相关的题很容易想到递归或者利用栈。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 递归
   public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
   	ArrayList<Integer> arrayList = new ArrayList<>();
   	return help(listNode, arrayList);
   }
   public ArrayList<Integer> help(ListNode listNode,ArrayList<Integer> arrayList) {
   	if (listNode != null) {
		help(listNode.next, arrayList);
		arrayList.add(listNode.val);
	}
   	return arrayList;
   }
   // 辅助栈
   public ArrayList<Integer> printListFromTailToHead3(ListNode listNode) {
   	ArrayList<Integer> arrayList = new ArrayList<>();
   	Deque<ListNode> stack = new LinkedList<>();
   	while(listNode != null) {
   		stack.push(listNode);
   		listNode = listNode.next;
   	}
   	while(!stack.isEmpty()) {
   		arrayList.add(stack.pop().val);
   	}
   	return arrayList;
   }

复杂度分析：

递归：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(n)。

辅助栈：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(n)。