題目描述

輸入一個連結串列，按連結串列從尾到頭的順序返回一個ArrayList。

示例輸入、輸出如圖所示：

思路分析

1.遞迴呼叫：遞迴呼叫，藉助JVM的棧實現反轉，面試時不建議。

2.陣列插入：每次將資料插入到陣列的第一個位置，實現反轉，涉及陣列資料移動，時間複雜度,空間複雜度。

3.棧LIFO：遍歷一遍連結串列，將資料插入棧，運用棧的LIFO特性實現反轉，推薦使用，時間複雜度,空間複雜度。

實現方案

1.遞迴呼叫

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

2.陣列插入

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

3.棧LIFO

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