从尾到头打印链表

题目描述
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

//结构体
class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}

解析
首先想到的是存储到ArrayList中在反转，可以利用栈Stack的原理，new一个Stack，把链表遍历到栈中，栈再遍历到ArrayList中。

因为ArrayList提供了根据下标插入的方法add(int index, E element)，在遍历插入时，每次都插入在0下标位置，也可以实现，但是每次都要挪动数组。

其次，利用递归的原理，也就是一直递归到最后一个节点再依次向前添加（如果节点不为null，则接着调用自身）。

Java

/**
 * 每次在下标0处插入
 * 运行时间：22ms
 * 占用内存：9376k
 */
public ArrayList<Integer> printListFromTailToHead1(ListNode listNode) {
    ArrayList<Integer> arrayList = new ArrayList<>();
    while (listNode != null) {
        arrayList.add(0, listNode.val);
        listNode = listNode.next;
    }
    return arrayList;
}

/**
 * 递归
 * 运行时间：21ms
 * 占用内存：9348k
 */
ArrayList<Integer> arrayList = new ArrayList<>();
public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
    if (listNode != null) {
        printListFromTailToHead2(listNode.next);
        arrayList.add(listNode.val);
    }
    return arrayList;
}

/**
 * 利用栈
 * 运行时间：22ms
 * 占用内存：9276k
 */
public ArrayList<Integer> printListFromTailToHead3(ListNode listNode) {
    Stack<Integer> stack = new Stack<>();
    while (listNode != null) {
        stack.push(listNode.val);
        listNode = listNode.next;
    }
    ArrayList<Integer> arrayList = new ArrayList<>();
    while (!stack.isEmpty()) {
        arrayList.add(stack.pop());
    }
    return arrayList;
}

Python

Python字符串的逆向输出真的是妙不可言。
另外递归用“+”添加元素。

class PrintListFromTailToHead:
    # 递归
    # 运行时间：30ms
    # 占用内存：5728k
    def printListFromTailToHead(self, listNode):
        if listNode is None:
            return []
        return self.printListFromTailToHead(listNode.next) + [listNode.val]

    # 逆向输出
    # 运行时间：33ms
    # 占用内存：5736k
    def printListFromTailToHead(self, listNode):
        res = []
        while listNode:
            res.append(listNode.val)
            listNode = listNode.next
        # 逆向输出
        return res[::-1]

    class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None