题目

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

1.png

非递归

listNode是一个链表，只能从头遍历到尾，但是又需要从尾到头输出，符合栈特性，先进后出

• 使用ArrayList中的add进行重载，每次都往新的ArrayList中的索引第一位添加数据

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        //临时变量
        ListNode temp = listNode;
        while(temp != null){
            //每次都往索引为0的地方添加数据
            list.add(0,temp.val);
            //下一个
            temp = temp.next;
        }
        return list;
    }
}

• 使用栈（Stack）

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        //创建一个栈
        Stack<Integer> stack = new Stack();
        //遍历集合
        while(listNode != null){
            //将集合中数据存人栈中
            stack.add(listNode.val);
            listNode = listNode.next;
        }
        ArrayList<Integer> list = new ArrayList<>();
        //根据栈的特性，输出栈数据然后再存入新的集合中
        while(!stack.isEmpty()){
            list.add(stack.pop());
        }
        return list;
    }
}

栈

递归

要逆序打印链表 1->2->3（3,2,1)，可以先逆序打印链表 2->3(3,2)，最后再打印第一个节点 1。而链表 2->3 可以看成一个新的链表，要逆序打印该链表可以继续使用求解函数，也就是在求解函数中调用自己，这就是递归函数

public class Solution {
    ArrayList<Integer> list = new ArrayList();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode != null){
            printListFromTailToHead(listNode.next);
            list.add(listNode.val);  
        }
        return list;
    }
}
=======================================
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    ArrayList<Integer> ret = new ArrayList<>();
    if (listNode != null) {
        ret.addAll(printListFromTailToHead(listNode.next));
        ret.add(listNode.val);
    }
    return ret;
}

• 使用头插法

参考

CS-Notes
何海涛. 剑指 Offer[M]. 电子工业出版社, 2012.