jz06.从尾到头打印链表

题目描述

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

示例 1：

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

题解

栈

利用栈先入后出的性质, 按顺序将每个节点入栈, 然后向数组中弹出, 生成的数组就是完成逆序的链表.

public int[] reversePrint(ListNode head) {
    Stack<Integer> stack = new Stack<>();
    while (head!=null){
        stack.push(head.val);
        head = head.next;
    }

    int size = stack.size();
    int[] res = new int[size];
    for (int i = 0; i < size; i++) {
        res[i] = stack.pop();
    }
    return res;
}

递归

先递归到链表的末尾, 然后将节点加入, 类似树的后序遍历

public int[] reversePrint2(ListNode head) {
    ArrayList<Integer> list = new ArrayList<>();
    recur(head, list);
    int[] res = new int[list.size()];
    for (int i = 0; i < list.size(); i++) {
        res[i] = list.get(i);
    }
    return res;
}

private void recur(ListNode head, ArrayList<Integer> list){
    if (head==null)
        return;
    recur(head.next, list);
    list.add(head.val);
}