题目

剑指 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)\)的空间
11-07 08:39