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

小咪咪 2022-11-26 06:54 69阅读 0赞

# 题目描述 #

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

# 解答 #

最初的思路是用一个栈存着，再依次pop（）到ArrayList里面。

import java.util.ArrayList;
    import java.util.Stack;
    public class Solution {
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
            ListNode index = listNode;
            Stack<Integer> newSpace = new Stack<Integer>();
            ArrayList<Integer> result = new ArrayList<Integer>();
                    
            while(index!=null){
                newSpace.push(index.val);
                index = index.next;
            }
            
            while(!newSpace.isEmpty()){
                for(int i = 0;i<newSpace.size();i++){
                    result.add(newSpace.pop());
                }
            }
            return result;
        }
    }

--------------------

时间复杂度：O(2n)    空间复杂度：O(n)

看到竟然还可以用**递归**来解答。

import java.util.ArrayList;
    public class Solution {
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
            ArrayList<Integer> result = new ArrayList<Integer>();
            operate(listNode, result);
            return result;
        }
        public void operate(ListNode listnode, ArrayList<Integer> result){
            if(listnode!=null){
                operate(listnode.next,result);
                result.add(listnode.val);
            }
        }
    }