题目描述

将链表的数据反向打印

样例

输入：[5,3,2]
输出：[2,3,5]

算法1

(暴力遍历)

时间复杂度O(n^2)

想法：先遍历，将数值保存在动态数组中，实例化一个整型数组，大小是动态数组的大小，

遍历动态数组，将数值反向存放在整型数组中

static class Solution {
    public int[] printListReversingly(ListNode head) {
        if(head==null) return null;//头节点是空指针
        ArrayList<Integer> nums=new ArrayList<Integer>();
        ListNode current=head;
        while(true) {
            nums.add(current.val);
            current=current.next;
            if(current==null) {
                break;
            }
        }
        int[] num=new int[nums.size()];
        for (int i = 0; i < num.length; i++) {
            num[i]=nums.get(nums.size()-1-i);
        }
        return num;
    }
}

算法2

递归

时间复杂度 O(n)

想法

参考各位使用尾递归的JAVA代码,

static class Solution_new {
        int count=0;
      //  int i=0;
        int[] nums;

    public int[] printListReversingly(ListNode head) {
        if(head==null) return null;//头节点是空指针
        work(head);
        return nums;
    }
    private void work(ListNode head) {
        count++;
        if(head.next!=null) {
            work(head.next);
        }
        else {//else语句块只会执行一次，就是在没有下一个结点的时候执行
            //执行这里时，说明没有下一个节点了，此时的count就是所有的节点数
            nums=new int[count];//这时候需要实例化整数数组，
        //  i=count;//i作为辅助的变量，存放节点总数
            count=0;//将位置清零
        }
    //  nums[i-count]=head.val;//这个节点的所在的数组位置=总数-当前的count值
    //  count--;//下一个数的坐标值=总数-count
        //也可以这么写
        nums[count]=head.val;
        count++;//下一个节点存放位置的下标
    }

}