题目描述

blablabla

样例

算法1

(暴力枚举) $O(2n)$

先计算出节点的个数，然后开辟响应大小的数组，再将链表的值填入数组

Java 代码

class Solution {
    public int[] printListReversingly(ListNode head) {
        int count = 0;
        ListNode node = head;
        while(node != null ){
            node = node.next;
            count++;  
        } 
        int[] res = new int[count];
        while(head!=null ){
            res[--count] = head.val;
            head = head.next;
        }
        return res;
    }

}

算法2

(递归) $O(n)$

利用递归和链表特点，当节点为空后，创建数组，在回溯的过程中，将链表节点的值放入相应位置

Java 代码

class Solution {
    int count = 0;
    int[] res = null;

    public void dfs(ListNode node,int deep){
        if(node == null){
            res = new int[deep];
            count = deep;
            return;
        }
        dfs(node.next, deep + 1);
        res[count - (deep + 1)] = node.val;
    }

    public int[] printListReversingly(ListNode head) {
        dfs(head,0);
        return res;
    }

}