从尾到头打印链表

题目描述

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

示例 1：

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

限制：
0 <= 链表长度 <= 10000

题目链接

Leetcode

题目解答

解法一

从尾到头打印链表刚好符合先进后出的情况，自然我们会想到使用栈这种数据结构，先遍历链表节点入栈，然后按元素出栈顺序构建新的数组就能得到想要的结果。

时间复杂度:$O(n)$ 空间复杂度:$O(n)$

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        LinkedList<Integer> stack = new LinkedList<>();
        ListNode curr = head;
        while (curr != null) {
            stack.addFirst(curr.val);
            curr = curr.next;
        }
        int[] res = new int[stack.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = stack.pollFirst();
        }
        return res;
    }
}

执行用时：1 ms, 在所有 Java 提交中击败了72.23%的用户
内存消耗：39 MB, 在所有 Java 提交中击败了64.50%的用户

解法二

还有一种解法也是比较容易想到的，就是先获取链表的长度，然后创建一个同等大小的数组，链表从前往后遍历，数组从后往前填充元素，少了入栈和出栈的时间开销，这种处理方式时间性能会更好一些。

时间复杂度:$O(n)$ 空间复杂度:$O(n)$

class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode curr = head;
        int count = 0;
        while (curr != null) {
            count++;
            curr = curr.next;
        }
        curr = head;
        int[] res = new int[count];
        for (int i =0;i<res.length;i++) {
            count--;
            res[count] = curr.val;
            curr = curr.next;
        }
        return res;
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：39 MB, 在所有 Java 提交中击败了66.36%的用户

解法三

除了使用栈，我们还可以尝试用递归的方式处理，本质上递归是调用系统的堆栈，和栈原理是一致的，不过还需要借助辅助的函数和变量。

时间复杂度:$O(n)$ 空间复杂度:$O(n)$

class Solution {

    public int idx;
    public int[] res;

    public int[] reversePrint(ListNode head) {
        recursive(head, 0);
        return res;
    }

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

执行用时：1 ms, 在所有 Java 提交中击败了72.23%的用户
内存消耗：39.8 MB, 在所有 Java 提交中击败了12.01%的用户