题目描述

从尾到头输出单链表的值到数组

样例

输入：1->2->3 返回 [3,2,1]

算法1

(利用栈的性质，所有元素只遍历一次，所以时间复杂度$O(n)$， 空间复杂度$O(n)$)

Java代码

public int[] printListReversingly(ListNode head) {
        if (head == null) {
            return new int[0];
        }
        int n = 0;
        LinkedList<Integer> stack = new LinkedList<>();
        while (head != null) {
            stack.push(head.val);
            head = head.next;
            n++;
        }
        int[] res = new int[n];
        n = 0;
        while(stack.size() > 0) {
            res[n++] = stack.pop();
        }
        return res;
    }

算法2

(尾递归) 时间复杂度 $O(n)$ 空间复杂度$O(n)$

Java 代码

public int[] printListReversingly(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode tmp = head;
        int count = 0;
        while (tmp != null) {
            tmp = tmp.next;
            count++;
        }
        int[] res = new int[count];
        helper(head, res, count - 1);
        return res;
    }
    public void helper(ListNode head, int[] res, int i) {
        if (head == null) {
            return;
        }
        helper(head.next, res , i - 1);
        res[i] = head.val;
    }