问题描述

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

示例 1：

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

输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

自己的解法

对于这道题，自己的思路是，先将链表顺序输出到一个list集合中，创建一个大小等于集合size的数组，然后倒序遍历这个集合将元素插入到数组中，代码如下：

public int[] reversePrint(ListNode head) {       ListNode temp = head;       List<Integer> array = new ArrayList();       int i = 0;       while(temp!=null){           array.add(temp.val);           temp = temp.next;                   }       int[] result = new int[array.size()];       for(int j=array.size()-1;j>=0;j--){           result[i++] = array.get(j);       }       return result;   }

官方的解法是，利用栈的后进先出的特点，将链表元素顺序压入栈中，然后弹栈，就可以实现链表的反向输出。代码如下：

public int[] reversePrint(ListNode head) {       Stack<ListNode> stack = new Stack();       ListNode temp = head;       while(temp!=null){           stack.push(temp);           temp = temp.next;       }       int size = stack.size();       int[] array = new int[size];       for(int i = 0;i<size;i++){           array[i] = stack.pop().val;       }       return array;   }

在编写官方解法的代码第一次运行时碰到了一个问题，就是没有使用一个变量来保存栈的size，而是在for循环中使用了stack的size方法，并且在循环体中使用了pop方法，这样的话，栈的大小会改变，输出的结果不对。

其他解法

在看别人的解法时发现了一个采用递归的方法，递归到最后一个点向前回溯，将回溯到的节点的值添加到集合中去，最后将集合转换为数组，这种方法比起我自己的方法省去了反转集合的一步，但是也还是要遍历一次，所以结果出入不大。

List<Integer> list = new ArrayList();   public int[] reversePrint(ListNode head) {       recur(head);       int size = list.size();       int[] array = new int[size];       for(int i = 0;i<size;i++){           array[i] = list.get(i);       }       return array;   }   public void recur(ListNode head){       if(head==null){           return;       }       recur(head.next);       list.add(head.val);   }