圖解劍指 offer 第三題： 從尾到頭打印鏈表

題目描述

輸入一個鏈表，按鏈表值從尾到頭的順序返回一個 ArrayList 。

題目解析

這道題目描述很簡潔，就一句話，很好理解。

圖 1

解法

解法一

初看題目意思就是輸出的時候鏈表尾部的元素放在前面，鏈表頭部的元素放在後面。這不就是 先進後出，後進先出 麼。

什麼數據結構符合這個要求？

棧 ！

動畫 2

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<integer> printListFromTailToHead(ListNode listNode) {
 //使用 棧 這種數據結構
 Stack<integer> stack = new Stack<>();
 //將鏈表元素全部存放在 棧 裡面
 while (listNode != null) {
 stack.add(listNode.val);
 listNode = listNode.next;
 }
 ArrayList<integer> ret = new ArrayList<>();
 //取出棧裡面的元素
 while (!stack.isEmpty())
 ret.add(stack.pop());
 return ret;
}
}
/<integer>/<integer>/<integer>

解法二

第二種方法也比較容易想到，通過鏈表的構造，如果將末尾的節點存儲之後，剩餘的鏈表處理方式還是不變，所以可以使用遞歸的形式進行處理。

代碼如下：

import java.util.ArrayList;
public class Solution {
public ArrayList<integer> printListFromTailToHead(ListNode listNode) {
 ArrayList<integer> ret = new ArrayList<>();
 if (listNode != null) {
 ret.addAll(printListFromTailToHead(listNode.next));
 ret.add(listNode.val);
 }
 return ret;
} 

}
/<integer>/<integer>

解法三

如果你還知道鏈表的更多性質的話，肯定能想到用 頭插法 為逆序的特點來解決。

頭插法：將鏈表的左邊稱為鏈表頭部，右邊稱為鏈表尾部。頭插法是將右邊固定，每次新增的元素都在左邊頭部增加。

頭插法

public ArrayList<integer> printListFromTailToHead(ListNode listNode) {
 // 頭插法構建逆序鏈表
 ListNode head = new ListNode(-1);
 while (listNode != null) {
 ListNode memo = listNode.next;
 listNode.next = head.next;
 head.next = listNode;
 listNode = memo;
 }
 // 構建 ArrayList
 ArrayList<integer> ret = new ArrayList<>();
 head = head.next;
 while (head != null) {
 ret.add(head.val);
 head = head.next;
 }
 return ret;
}
/<integer>/<integer>

End

今日問題：

你認為棧和隊列最大的一個區別是什麼？優先隊列和堆是什麼關係？

打卡格式：

打卡 X 天，答：xxx 。

閱讀更多 五分鐘學算法 的文章

關鍵字: new next ret