力扣 – 剑指 Offer 06. 从尾到头打印链表.md

• 2021 年 11 月 6 日
• 筆記
• 栈, 算法与题解, 递归

题目

剑指 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)\)的空间