目錄
1.題目
2.解法
2.1堆疊
2.2遞回
3.復雜度
1.題目
輸入一個鏈表的頭節點，從尾到頭反過來回傳每個節點的值（用陣列回傳），
題目來源：力扣（LeetCode）
2.解法
2.1堆疊
堆疊的特點是先進后出，所以我們創建一個堆疊，逐個將節點壓入堆疊內，然后建立一個陣列，將堆疊內的節點數值逐個彈出
class Solution {
public int[] reversePrint(ListNode head) {
Stack<ListNode> stack = new Stack<ListNode>();//創建一個堆疊
ListNode cur = head;
//將節點壓堆疊
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
int size = stack.size();//堆疊的長度
int[] array = new int[size];//創建一個和堆疊一樣長的陣列
//出堆疊入陣列
for (int i = 0; i < size; i++) {
array[i] = stack.pop().val;
}
return array;
}
}
2.2遞回
public class PrintList {
ArrayList<Integer> cur = new ArrayList<Integer>();
public int[] reversePrint(ListNode head) {
recur(head);
int[] array = new int[cur.size()];
for (int i = 0; i <array.length; i++) {
array[i] = cur.get(i);
}
return array;
}
public void recur(ListNode head) {
if(head == null) {
return ;
}
recur(head.next);
cur.add(head.val);
}
}
3.復雜度
1.堆疊
時間復雜度：O(n)，正向遍歷一遍鏈表，然后從堆疊彈出全部節點，等于又反向遍歷一遍鏈表，
空間復雜度：O(n)，額外使用一個堆疊存盤鏈表中的每個節點，
2.遞回
時間復雜度：O(n) 遍歷鏈表，遞回 NN次，
空間復雜度：O(n) 系統遞回需要使用 O(N)的堆疊空間
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/402471.html
標籤：其他
上一篇：詳解異步多執行緒使用中的常見問題