題目描述

輸入一個鏈表的頭節點，按鏈表從尾到頭的順序返回每個節點的值（用數組返回）。

如輸入{1,2,3}的鏈表如下圖:

返回一個數組為[3,2,1]

0 <= 鏈表長度 <= 10000

示例1

輸入：

{1,2,3}

返回值：

[3,2,1]

示例2

輸入：

{67,0,24,58}

返回值：

[58,24,0,67]

思路及解答

⾸先我們需要想⽤哪些解法可以解，⼤概有如下：

• 使⽤棧
• 使⽤遞歸調⽤
• 頭插法

藉助棧實現

先把元素⾥⾯的元素從頭到尾遍歷取出放在棧⾥⾯，然後再把棧的元素去出來放在ArraList ⾥⾯。主要利⽤了棧的先進後出的規則，這樣就可以實現倒序的功能。Java 代碼實現如下：

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> results = new ArrayList<>();
        while (!stack.isEmpty()) {
            results.add(stack.pop());
        }
        return results;
    }
}

遞歸調⽤

前⾯我們能想到棧，那麼我們何必⾃⼰實現呢？其實⽅法的調⽤過程，就是⼀個天然的棧調⽤的過程呀，只需要判斷當前節點是不是為空，為空則不輸出，不為空則遞歸下⼀個節點，對下⼀個節點處理之後，把結果使⽤ArrayList.addAll() 加到結果中，再把⾃身加到結果中即可：

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> results = new ArrayList<>();
        if(listNode!=null){
            // 對後⾯的元素進⾏處理
            results.addAll(printListFromTailToHead(listNode.next));
            // 最後添加⾃身
            results.add(listNode.val);
        }
        return results;
    }
}

頭插法

遍歷每⼀個節點，然後把它插⼊到頭部，這樣⼀直遍歷到尾的時候，就相當於將整個鏈表都反轉⼀遍了，然後再從頭到尾遍歷放到ArryList 即可。

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ListNode head = new ListNode(-1);
        while(listNode!=null){
            // 先把當前node的next保存起來
            ListNode temp = listNode.next;
            // 把當前節點的next指針指向head的下⼀個節點
            listNode.next = head.next;
            // 把head的next指向當前節點
            head.next = listNode;
            // 將遍歷的指針指向了遍歷的下⼀個元素
            listNode = temp;
        }
        ArrayList<Integer> results = new ArrayList<>();
        head = head.next;
        
        // 遍歷輸出
        while(head!=null){
            results.add(head.val);
            head = head.next;
        }
        return results;
    }
}