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

理想

2022-1-22

每日一题

这道题目比较简单，两种解题方法都是可以想出来的，代码部分就没有写注释哦，水一道题目😋

题目

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

示例 1：

输入：head = [1,3,2]

输出：[2,3,1]
限制：

0 <= 链表长度 <= 10000

解题方法一

/**
     * 首先遍历链表得到长度，然后创建一定长度数组，最后再次遍历链表，同时将节点存入数组 数组从后往前存放
     * 注意 链表为空返回的是[] 而不是null
     * @param head
     * @return
     */
    public int[] reversePrint(ListNode head) {
        // TMD 如果为空返回[]!!
//        if (head == null){
//            return null;
//        }
        int listLen = 0;
        ListNode cur = head;
        while (cur != null){
            listLen++;
            cur = cur.next;
        }
        int[] resultArr = new int[listLen];
        for (int i = listLen - 1; i >=0 ; i--) {
            resultArr[i] = head.val;
            head = head.next;
        }
        return resultArr;
    }

解题方法二

/**
     * 使用栈结构 先进后出特点 依次压栈然后依次弹栈存放数组中
     * 时间复杂度：O(n)。正向遍历一遍链表，然后从栈弹出全部节点，等于又反向遍历一遍链表。
     * 空间复杂度：O(n)。额外使用一个栈存储链表中的每个节点。
     *
     * @param head
     * @return
     */
    public int[] reversePrint2(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        while (head != null){
            stack.add(head.val);
            head = head.next;
        }
        int[] resultArray = new int[stack.size()];
        for (int i = 0; i < resultArray.length; i++) {
            resultArray[i] = stack.pop();
        }
       return resultArray;
    }