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

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

递归

public class Solution {
    public int[] reversePrint(ListNode head) {
        // 用于存储结果
        List<Integer> list = new ArrayList<>();
        // 递归方法
        recursion(head, list);
        // 将 List 转化为 int[]
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }
    /**
     * 递归打印，思路类似二叉树后序遍历
     * @param node 结点
     * @param list 存储结果
     */
    private void recursion(ListNode node, List list) {
        if (node != null) {
            recursion(node.next, list);
            // 在递归调用的的下方打印
            list.add(node.val);
        }
    }
}

递归2

增加记录链表长度，简化掉 List 转数组的操作

class Solution {
    // 记录返回结果
    private int[] res;
    // 记录链表总长度
    private int count = 0;
    // 赋值数组时记录索引
    private int index = 0;
    public int[] reversePrint(ListNode head) {
        recursion(head);
        return res;
    }
    public void recursion(ListNode head) {
        if (head != null) {
            count ++;
            recursion(head.next);
            res[index ++] = head.val;
        } else {
            res = new int[count];
        }
    }
}

使用辅助栈

执行用时：2 ms, 在所有 Java 提交中击败了38.48% 的用户 内存消耗：38.9 MB, 在所有 Java 提交中击败了77.98% 的用户

class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        while (head != null) {
            stack.add(head.val);
            head = head.next;
        }
        int[] res = new int[stack.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = stack.pop();
        }
        return res;
    }
}