剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

方法一

先遍历整个链表，求得链表的长度 $n$，然后创建一个长度 $n$ 的数组 $ans$。倒序遍历数组 $ans$，而链表正序遍历，将链表的值赋值到数组中。

代码：

public int[] reversePrint(ListNode head){
    if(head == null) {
        return new int[0];
    }
    int len = 0;
    ListNode p = head;
    while(p != null) {
        len++;
        p = p.next;
    }
    int[] ans = new int[len];
    for(int i = len-1; i >= 0; i--){
        ans[i] = head.val;
        head = head.next;
    }
    return ans;
}

复杂度分析

• 时间复杂度$O(N)$：遍历链表和遍历数组的操作均为 $O(1)$ 时间。
• 空间复杂度$O(N)$：$ans$ 数组需要 $O(N)$ 空间。

方法二

使用辅助栈，借助栈的先进后出的特点，将链表的元素先全部压入栈中，然后再弹出。

代码：

public int[] reversePrint(ListNode head){
    if(head == null) {
        return new int[0];
    }
    Deque<Integer> stack = new LinkedList<>();
    while(head != null) {
        stack.push(head.val);
        head = head.next;
    }
    int[] ans = new int[stack.size()];
    int k = 0;
    while(!stack.isEmpty()){
        ans[k++] = stack.pop();
    }
    return ans;
}

复杂度分析

• 时间复杂度 $O(N)$：入栈和出栈共使用 $O(N)$ 时间。
• 空间复杂度 $O(N)$：辅助栈 $stack$ 和 $ans$ 共使用 $O(N)$ 空间。