從尾到頭列印鏈表
輸入一個鏈表的頭節點，從尾到頭反過來回傳每個節點的值（用陣列回傳），
示例 1：
輸入：head = [1,3,2] 輸出：[2,3,1]
限制：
0 <= 鏈表長度 <= 10000
我的思路：
先從頭到尾遍歷鏈表，將鏈表節點中的值存入新開辟的陣列空間，再將陣列順序倒置，
C++代碼如下：
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 vector<int> reversePrint(ListNode* head) { 12 vector<int> list; 13 ListNode* p = head; 14 while(p != NULL){ 15 list.push_back(p->val); //將每個鏈表節點的值都存在陣列中 16 p = p->next; 17 } 18 int temp; 19 for(int i=0;i<list.size()/2;i++){ //再將陣列首尾倒置 20 temp = list[i]; 21 list[i] = list[list.size()-1-i]; 22 list[list.size()-1-i] = temp; 23 } 24 return list; 25 } 26 };
其他參考思路：均用到了堆疊，
方法一：遞回法
解題思路：
利用遞回： 先走至鏈表末端，回溯時依次將節點值加入串列 ，這樣就可以實作鏈表值的倒序輸出，
Python 演算法流程：
遞推階段： 每次傳入 head.next ，以 head == None（即走過鏈表尾部節點）為遞回終止條件，此時回傳空串列 [] ，
回溯階段： 利用 Python 語言特性，遞回回溯時每次回傳 當前 list + 當前節點值 [head.val] ，即可實作節點的倒序輸出，
Java 演算法流程：
遞推階段： 每次傳入 head.next ，以 head == null（即走過鏈表尾部節點）為遞回終止條件，此時直接回傳，
回溯階段： 層層回溯時，將當前節點值加入串列，即tmp.add(head.val)，
最終，將串列 tmp 轉化為陣列 res ，并回傳即可，
復雜度分析：
時間復雜度 O(N)： 遍歷鏈表，遞回N次，
空間復雜度 O(N)： 系統遞回需要使用O(N)的堆疊空間，
方法二：輔助堆疊法
解題思路：
鏈表特點： 只能從前至后訪問每個節點，
題目要求： 倒序輸出節點值，
這種 先入后出 的需求可以借助 堆疊 來實作，
演算法流程：
入堆疊： 遍歷鏈表，將各節點值 push 入堆疊，（Python? 使用 append() 方法，?Java?借助 LinkedList 的addLast()方法），
出堆疊： 將各節點值 pop 出堆疊，存盤于陣列并回傳，（Python? 直接回傳 stack 的倒序串列，Java ?新建一個陣列，通過 popLast() 方法將各元素存入陣列，實作倒序輸出），
復雜度分析：
時間復雜度 O(N)： 入堆疊和出堆疊共使用 O(N) 時間，
空間復雜度 O(N)： 輔助堆疊 stack 和陣列 res 共使用 O(N)的額外空間，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/65507.html
標籤：其他