面试题06. 从尾到头打印链表

题目描述：

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

示例 1：

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

限制：

0 <= 链表长度 <= 10000

思路(栈)：

1、这道题的特点是元素后进先出，符合栈的特征；
2、从头到尾遍历链表，依次压入栈中；
3、再将栈中元素依次弹出到数组中；
4、返回数组。

Java解法(栈)：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode tmp = head;
        while( tmp != null)
        {
            stack.push(tmp.val);
            tmp = tmp.next;
        }
        int size = stack.size();
        int[] ans = new int[size];
        for(int i= 0; i < size; i++)
        {
            ans[i] = stack.pop();
        }
        return ans;
    }
}

python3解法：

思路2(递归)：

既然能够想到利用栈来实现，而递归的本质其实就是一个栈结构，因此我们很自然能否想到用递归来实现；
1、递推阶段： 每次传入 head.next ，以 head == null（即走过链表尾部节点）为递归终止条件，此时直接返回。
2、回溯阶段： 层层回溯时，将当前节点值加入列表，即list.add(head.val)。
3、最终，将列表 list 转化为数组 ans ，并返回即可。

Java解法(递归)：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    ArrayList<Integer> list = new ArrayList<Integer>();
    public int[] reversePrint(ListNode head) {
        res(head);
        int size = list.size();
        int[] ans = new int[size];
        for(int i =0; i < size; i++)
        {
            ans[i] = list.get(i);
        }
        return ans;
    }
    public void res(ListNode head){
        if(head == null) return;
        res(head.next);
        list.add(head.val);
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof