剑指03.从尾到头打印链表

题目描述

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

 

思路

方法一：借助栈的“后进先出”实现。从头到尾遍历链表，每经过一个节点，就把节点压入栈中。遍历完后，再从栈顶逐个输出节点的值。

方法二：用递归实现（递归的本质就是一个栈结构）。每访问到一个节点的时候，先递归输出它后面的节点，再输出该节点自身的值。

方法一

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> stack = new Stack<Integer>();
        while (listNode != null){
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        ArrayList<Integer> list = new ArrayList<Integer>();
        while (!stack.isEmpty()){
            list.add(stack.pop());
        }
        return list;
    }
}

☆☆☆方法二（递归的精髓0.0）

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    ArrayList<Integer> list = new ArrayList<Integer>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if (listNode != null){
            printListFromTailToHead(listNode.next);
            list.add(listNode.val);
        }
        return list;
    }
}

 Note：最后的return只是最里面的一层结束了，然后需要回到上一层，所有的层回完了才算结束；  return之后继续添加数值，是因为添加值的操作在递归的那行之后。