题目

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

思路1（递归）

• 首先先遍历整个脸表，计算出链表的长度（用于初始化数组）。然后进行递归，从链表头部递归到尾部，这期间什么都不做，直到递归到最后一个节点的时候开始返回，开始返回的同时吧当前节点的值加入到res数组

代码

class Solution {

    int[] res;

    int index = 0;

    public int[] reversePrint(ListNode head) {

        // 先统计链表的总节点数量

        int count = 0;

        ListNode temp = head;

        while (temp != null) {

            count++;

            temp = temp.next;

        }

        res = new int[count];

        // 进行递归

        help(head);

        // 输出结果

        return res;

    }

    public void help(ListNode node) {

        if (node == null) {

            return;

        }

        help(node.next);

        res[index++] = node.val;

    }

}

复杂度分析

• 时间复杂度：\(O(N)\)，遍历一遍链表所花费的时间
• 空间复杂度：\(O(N)\)，递归所需要的空间

思路2（栈）

• 使用栈的先进后出FILO原则，顺序遍历链表，将链表的元素依次加入到栈中。接下来将栈的元素一个个pop弹出来放到res数组中即可（因为是先进先出，所以此时栈的最后一个元素要先弹出，因此可以实现从尾到头遍历）

代码

class Solution {

    public int[] reversePrint(ListNode head) {

        // 将链表的元素依次入栈

        LinkedList<Integer> stack = new LinkedList<>();

        while (head != null) {

            stack.push(head.val);

            head = head.next;

        }

        int[] res = new int[stack.size()];

        // 将栈元素弹出放到res中

        int index = 0;

        while (!stack.isEmpty()) {

            res[index++] = stack.pop();

        }

        return res;

    }

}

复杂度分析

• 时间复杂度：\(O(N)\)
• 空间复杂度：\(O(N)\)，辅助栈使用了\(O(N)\)的空间