题目

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

看到题目第一反应是用栈，将节点一个一个压入栈中，然后弹栈打印节点即可，难度不大，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
public ArrayList<Integer> printListFromTailToHead(ListNode listNode){
    Stack<ListNode> stack = new Stack<>();
    while (listNode != null) {
        stack.push(listNode);
        listNode = listNode.next;
    }
    ArrayList<Integer> res = new ArrayList<>();
    while(!stack.empty()){
        res.add(stack.pop().val);
    }
    return res;
}

上面的算法借助了栈，使用了 O(n) 的空间。有没有更好的解法呢？其实能用栈做的事情，用递归都可以做。递归其实也使用了函数栈。

递归的算法只需要先递归下一个节点，等函数执行完之后再打印节点即可。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    ArrayList<Integer> list = new ArrayList<>();
    search(listNode, list);
    return list;
}

private void search(ListNode node, ArrayList<Integer> list) {
    if (node != null) {
        search(node.next, list);
        list.add(node.val);
    }
}

这个算法时间复杂度为 O(n)，空间复杂度不算函数栈的话（一般不计算函数栈）是 O(1)。