輸入一個鏈表，按鏈表從尾到頭的順序回傳一個ArrayList
解法一：最簡單的想法，先排序，再逆序
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> integerList = new ArrayList<>();
while (listNode != null) {
integerList.add(listNode.val);
listNode = listNode.next;
}
// 不想呼叫庫函式也行，自己寫一個叭
Collections.reverse(integerList);
return integerList;
}
}
解法二：借助堆疊先進后出的原理，輔助實作逆序
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
private Stack<Integer> stack = new Stack<>();
private ArrayList<Integer> list = new ArrayList<>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
while(listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}
while(stack.size() > 0) {
list.add(stack.pop());
}
return list;
}
}
解法三：使用遞回思想，遞回其實也類似于堆疊的呼叫
public class Solution {
ArrayList<Integer> arrayList = new ArrayList<Integer>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode != null){
this.printListFromTailToHead(listNode.next);
arrayList.add(listNode.val);
}
return arrayList;
}
}
解法四：使用頭插法實作
對于 ArrayList 來說，陣列元素移動的開銷太大，不建議使用，但思路是不錯的
public class Solution {
private ArrayList<Integer> list = new ArrayList<>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
while(listNode != null) {
list.add(0, listNode.val);
listNode = listNode.next;
}
return list;
}
}
小結：涉及到逆序問題，可以往以下方面考慮
- 借助堆疊先進后出的特點
- 遞回也可以實作堆疊的作用
- 頭插法是把新結點插入首部，其余結點往后退，也是一個值得考慮的方案
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/19517.html
標籤：其他
上一篇：Markdown格式及語法