力扣 – 劍指 Offer 06. 從尾到頭打印鏈表.md

• 2021 年 11 月 6 日
• 筆記
• 棧, 算法與題解, 遞歸

題目

劍指 Offer 06. 從尾到頭打印鏈表

思路1（遞歸）

• 首先先遍歷整個臉表，計算出鏈表的長度（用於初始化數組）。然後進行遞歸，從鏈表頭部遞歸到尾部，這期間什麼都不做，直到遞歸到最後一個節點的時候開始返回，開始返回的同時吧當前節點的值加入到res數組

代碼

class Solution {
    int[] res;
    int index = 0;

    public int[] reversePrint(ListNode head) {
        // 先統計鏈表的總節點數量
        int count = 0;
        ListNode temp = head;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        res = new int[count];

        // 進行遞歸
        help(head);

        // 輸出結果
        return res;
    }

    public void help(ListNode node) {
        if (node == null) {
            return;
        }
        help(node.next);
        res[index++] = node.val;
    }
}

複雜度分析

• 時間複雜度：\(O(N)\)，遍歷一遍鏈表所花費的時間
• 空間複雜度：\(O(N)\)，遞歸所需要的空間

思路2（棧）

• 使用棧的先進後出FILO原則，順序遍歷鏈表，將鏈表的元素依次加入到棧中。接下來將棧的元素一個個pop彈出來放到res數組中即可（因為是先進先出，所以此時棧的最後一個元素要先彈出，因此可以實現從尾到頭遍歷）

代碼

class Solution {
    public int[] reversePrint(ListNode head) {
        // 將鏈表的元素依次入棧
        LinkedList<Integer> stack = new LinkedList<>();
        while (head != null) {
            stack.push(head.val);
            head = head.next;
        }

        int[] res = new int[stack.size()];
        // 將棧元素彈出放到res中
        int index = 0;
        while (!stack.isEmpty()) {
            res[index++] = stack.pop();
        }
        
        return res;
    }
}

複雜度分析

• 時間複雜度：\(O(N)\)
• 空間複雜度：\(O(N)\)，輔助棧使用了\(O(N)\)的空間