剑指offer（4）：从尾到头打印链表

本文主要是介绍剑指offer（4）：从尾到头打印链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

输入一个链表的头结点，从尾到头反过来打印出每个节点的值。

分析：
直接思路：将链表反转之后再从头到尾输出，但是这样会改变原始输入链表的结构。（Tips:面试中如果打算改变输入数据，最后问清楚面试官的而要求，是否允许修改。）通常打印是一个只读操作，假设此题不允许修改输入数据。

思路1：
从尾到头打印链表，实际上是一个先遍历的节点后输出的过程，即“先入后出”的栈结构。很容易想到用栈结构实现该目的。

牛客AC代码：

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {ArrayList<Integer> list = new ArrayList<Integer>();if(listNode == null)return list;// 栈结构实现“先进后出”，从尾到头打印Stack<ListNode> stack = new Stack<ListNode>();while(listNode != null) {stack.push(listNode);listNode = listNode.next;}while(!stack.empty()) {ListNode tmp = (ListNode)stack.pop();list.add(tmp.val);}return list;}
}

思路2：
考虑到递归调用本质上就是一个栈结构，自然想到可以用递归的方式实现：每次访问到一个节点，先递归输出它后面的节点，在输出该节点自身。

牛客AC代码：

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {ArrayList<Integer> arrayList=new ArrayList<Integer>();public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {if(listNode!=null){//先递归输出后面的节点，再输出自身this.printListFromTailToHead(listNode.next);arrayList.add(listNode.val);}return arrayList;}
}