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

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

题目

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

示例 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;
    }

 

微信关注

WeChat

阅读剩余
THE END