从后往前输出链表

题目

输入一个链表,从尾到头打印链表每个节点的值。

解题思路

  • 输出链表的值可以采用遍历的方法。但是遍历是从头到尾,因此可以采用栈的方式,先进后出的方式;
  • 递归在本质上就是一个栈结构,要实现反过来输出链表,在每次访问一个结点的时候,先递归输出他后面的结点,在输出该结点的本身

代码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.ArrayList;
import java.util.Stack;

/**
* Created by haigeek on 2017/7/13.
*/
class ListNode{
int val;
ListNode next=null;
ListNode(int val){
this.val=val;
}
}
//非递归的方式
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
Stack<Integer>stack=new Stack<>();
while (listNode!=null){
stack.push(listNode.val);
listNode=listNode.next;
}
ArrayList<Integer>list=new ArrayList<>();
while (!stack.isEmpty()){
list.add(stack.pop());
}
return list;
}
}
//递归的方式
public class Solution2{
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer>list=new ArrayList<>();
if(listNode!=null){
this.printListFromTailToHead(listNode.next);
list.add(listNode.val);
}
return list;
}
}

tips

了解java链表的一种定义方式

1
2
3
4
5
6
7
public class ListNode{
int val;
ListNode next=null;
ListNode(int val){
this.val=val;
}
}

加深对递归的认识