《剑指offer》系列 从尾到头打印链表（Java）

连接

牛客：从尾到头打印链表java

题目描述

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

思路

这题方法很经典，方法大体有3种：github

• 第一种是先申请一个栈空间，利用栈先进后出的特性，先将 list 里面的值 push进去，再进行 pop，获得的就是反转后的 list，这个方法思路很简单，缺点须要额外的空间。
• 第二种是翻转链表再打印（参考《剑指offer》系列 反转链表（Java）），这个虽然没有空间消耗，可是破坏了原来链表的结构。须要注意。
• 递归（内部其实也是栈的原理），既没有额外空间消耗，也没有破链表结构，就是思路不是那么清晰。

代码

这里给出递归实现的代码，其他两个思路的代码请参考 从尾到头打印链表web

import java.util.ArrayList;

public class Solution {

    ArrayList<Integer> arrayList = new ArrayList<Integer>();

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if (listNode == null)
            return arrayList;
        printListFromTailToHead(listNode.next);
        arrayList.add(listNode.val);
        return arrayList;
    }
}