从尾到头打印链表

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

方法一

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode node = head;
        int count = 0;
        // 计算链表里有多少个数字
        while(node!=null){
            ++count;
            node = node.next;
        }
        // 生成数组
        int arr[] = new int[count];
        // node重新赋值
        node = head;
        // 从后往前丢进数组里
        for(int i=count-1; i>=0; --i){
            arr[i] = node.val;
            node = node.next;
        }
        return arr;
    }
}

方法二

• 递归，时间O(n) 空间O(n)
  • 递推：传入head.next递归到最后一个点null，然后返回。
  • 回溯：在tmp[]里传入数值
  • 最后，tmp转换成数组，输出。

class Solution {
    ArrayList<Integer> tmp = new Array<Integer>();
    public int[] reversePrint(ListNode head) {
        recur (head);
        for(int i=0; i<res.length; i++) {
            res[i] = tmp.get(i);
        }
        return res;
    }
    void recur(ListNode head) {
        if(head == null) return;
        recur(head.next);
        tmp.add(head.val);
    }
}

方法三

• 辅助栈，时间O(n) 空间O(n)
  • 入栈：遍历链表，push入栈。
  • 出栈，pop出栈，存入数组。
  • 补充 Java中的java.util.LinkedList.addLast()方法用于在LinkedList的末尾插入特定元素。 句法： void addLast(Object element) java.util.LinkedList.removeLast() 方法移除并返回此列表的最后一个元素。

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