學習交流加

• 個人qq：
  1126137994
• 個人微信：
  liu1126137994
• 學習交流資源分享qq群：
  962535112

牛客網題目鏈接：
從尾到頭打印鏈表

文章目錄

• 題目描述
• 1、遞歸解法
• • 1.1、 遞歸解法一
  • • java代碼：
    • C++代碼
    • 分析：
  • 1.2 遞歸解法二
  • • java代碼：
    • C++代碼
• 2、使用棧
• • java代碼
  • C++代碼
• 總結

題目描述

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

本題較為簡單。有兩種解法：遞歸和使用棧循環。

1、遞歸解法

遞歸解法，也可以有兩種寫法。

1.1、 遞歸解法一

先上代碼，下面給解釋：

java代碼：

import java.util.ArrayList; public class Solution {ArrayList<Integer> arrayList=new ArrayList<Integer>();//注意這個ArrayList必須在方法體外定義public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {if(listNode!=null){this.printListFromTailToHead(listNode.next);arrayList.add(listNode.val);}return arrayList;} }

C++代碼

class Solution { public:vector<int> res;//注意這個vector必須在成員函數外定義vector<int> printListFromTailToHead(ListNode* head) {if(head!=nullptr){this->printListFromTailToHead(head->next);res.push_back(head->val);}return res;} };

分析：

這種遞歸的寫法，可以這么想：因為想要從尾到頭打印鏈表，那么如果此鏈表為空，則直接返回。如果只有一個節點，則將此節點打印。否則，遞歸打印頭結點以后的節點，直到遞歸到最后一個節點，那么，因為最后一個節點后面為空，所以返回上一級調用，上一級調用后的代碼為res.push_back(head->val);，此時的head剛好指向的最后的節點，將最后一個節點先放到數組。然后又返回到上一級的調用，將倒數第二個節點放到數組中。以此類推，直到將第一個節點放到數組中。

我們可以看如下圖示來分析上述遞歸的過程：

1.剛開始head指向節點1，不為空，將head指針指向下一個節點，然后遞歸調用函數到第2步

2.此時head依然不為空，將head指針指向下一個節點，然后遞歸調用函數到第3步

3.此時head依然不為空，將head指針指向下一個節點，然后遞歸調用函數到第4步

4.此時head依然不為空，將head指針指向下一節點，然后遞歸調用函數第5步

5.此時head指向空，遞歸結束，那么遞歸結束后，就需要返回到上一個遞歸的步驟，上一步驟是步驟4，那么執行遞歸語句的下一句：res.push_back(head->val)
（C++代碼），節點4的值放到數組中。然后再返回到步驟3，將節點3的值放入數組。以此類推，最終從后往前將所有鏈表節點的值放到數組中。

注意：此種遞歸方法中，返回數組的定義一定要放在函數體外面定義，如果放在函數體內定義，那么由于遞歸的層級不同，就會導致每次遞歸的時候都會重新定義一個數組，導致最后我們只能將第一個節點的值返回，結果肯定是錯的。在下一種遞歸的方法中，返回數組是可以定義在函數體內的，原因見下面解釋。

1.2 遞歸解法二

java代碼：

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

C++代碼

class Solution { public:vector<int> printListFromTailToHead(ListNode* head) {vector<int> res;if(head!=nullptr){if(head->next!=nullptr)res = printListFromTailToHead(head->next);res.push_back(head->val);}return res;} };

分析： 這種遞歸，實際上更好理解。首先，如果鏈表位空，則直接返回空數組。如果鏈表只有一個節點，則直接返回這個節點的值。如果這個鏈表不止一個節點，那么遞歸調用函數得到除了頭結點外后面的鏈表，得到后面的鏈表的從后往前打印（放到數組）的結果，然后再將之前的頭結點打印（放到數組末尾）。那么，最終得到的結果就是整個鏈表的從后往前打印的結果。

可以簡單的以下面圖示理解：
1.
剛開始，head指向頭結點，它后面還有節點（具體有幾個都無所謂）。將head指向下一個節點，然后遞歸調用函數。

2.現在是這樣的，從第1步過來，該遞歸調用函數求現在的這個鏈表的從后往前打印的結果。我們把現在這剩下的具有三個節點的鏈表，看成一個黑匣子整體，我的函數要對這個黑匣子求解它的倒序，然后這個函數返回了該鏈表的倒序的結果{4，3，2}。（其實這里面有好幾個遞歸的過程，但是我們不必將所有的遞歸過程想出來，只需要知道，現在我們可以將后面剩余的鏈表看成一個新鏈表，然后得到它的倒序就行）

3.得到后面的鏈表的倒序后，是存入數組的，最后我們再將頭結點的值，放到數組末尾res.push_back(head->val);，就可以得到{4，3，2，1}，這正是我們要的結果。

注意：這里的遞歸解法中，返回數組的定義，可以放到函數體內，也可以放到函數體外。與第一種遞歸的不同之處在于，這里我們可以將以下兩句話，放在同一個調用棧內看待，即
res =
printListFromTailToHead(head->next);這句話得到后面的鏈表的倒序后，就執行res.push_back(head->val);它們的執行，可以看成是在一個函數調用棧內進行的。而第一種遞歸調用中如果將返回數組定義在函數體內，每一個調用都是在一個新的函數調用棧，導致每一個函數棧中，都是一個新的返回數組，最終只能得到最頂層的函數棧中的數組，也就是鏈表的頭結點的值。

2、使用棧

遞歸解法雖然寫法簡單，但是遞歸調用需要重新開辟函數調用棧，開銷比較大。正常的解法實際上是使用棧來解決（棧這種數據結構本身就與遞歸有很大的聯系）。

可以遍歷鏈表，每遍歷一個節點就將節點的值壓入到棧中，直到遍歷完鏈表。最后再依次將棧中的元素彈出到返回的數組中。

java代碼

import java.util.Stack; import java.util.ArrayList; public class Solution {public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {Stack<Integer> st = new Stack<>();ListNode pListNode = listNode;while(pListNode != null){st.push(pListNode.val);pListNode = pListNode.next;}ArrayList<Integer> resArray = new ArrayList<>();while(!st.isEmpty()){resArray.add(st.pop());}return resArray;} }

C++代碼

class Solution { public:vector<int> printListFromTailToHead(ListNode* head) {vector<int> res;stack<int> st;ListNode* p = head;while(p != nullptr){st.push(p->val);p = p->next;}int len = st.size();for(int i = 0;i<len;++i){res.push_back(st.top());st.pop();}return res;} };

總結

• 理解遞歸的精髓，上述兩種遞歸的不一樣之處
• 理解遞歸與棧的關系

學習探討加：
qq：1126137994
微信：liu1126137994

總結

以上是生活随笔為你收集整理的【剑指offer - C++/Java】3、从尾到头打印链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。