題目一從尾到頭列印連結清單

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

1.描述

輸入一個連結清單的頭節點，從尾到頭反過來傳回每個節點的值（用數組傳回）。

2.示例

示例 1：

輸入：head = [1,3,2]
輸出：[2,3,1]

解法一疊代+輔助棧

解題思路

看到題不難想到最簡單的辦法就是借助一個輔助棧，順序周遊将節點值入棧，然後再依次出棧，就能實作倒序列印。

代碼

1  1 /**
 2  2  * Definition for singly-linked list.
 3  3  * struct ListNode {
 4  4  *     int val;
 5  5  *     ListNode *next;
 6  6  *     ListNode(int x) : val(x), next(NULL) {}
 7  7  * };
 8  8  */
 9  9 class Solution {
10 10 public:
11 11     vector<int> reversePrint(ListNode* head) {
12 12         vector<int> ans;//存儲答案
13 13         if(head == nullptr) return ans;//如果節點為空，輸出空數組
14 14         stack<int> tempAns;//輔助棧
15 15         ListNode* temp = head;
16 16         //順序周遊，将節點值壓棧
17 17         while(temp != nullptr){
18 18             tempAns.push(temp->val);
19 19             temp = temp->next;
20 20         }
21 21         while(!tempAns.empty()){//出棧直至棧為空
22 22             ans.push_back(tempAns.top());
23 23             tempAns.pop();
24 24         }
25 25         return ans;//傳回答案
26 26     }
27 27 };

複雜度分析

時間複雜度：

O(m)

。m為連結清單長度，周遊連結清單和出棧各需要

O(m)

時間。

空間複雜度：

O(m)

。輔助棧的空間消耗。

解法二遞歸

也可以借助遞歸一直遞推至連結清單尾部再層層回溯以實作反向輸出。這樣的方法代碼簡潔，但是調用函數時間消耗較大。

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         if(head==nullptr) return ans;//如果頭結點為空，傳回空數組
13         reversePrint(head->next);//遞推
14         ans.push_back(head->val);//回溯，持續存值
15         return ans;//傳回答案
16     }
17 
18     vector<int> ans;
19 };

O(m)

。遞歸的時間消耗

O(m)

。遞歸的空間消耗。

題目二反轉連結清單

連結：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

定義一個函數，輸入一個連結清單的頭節點，反轉該連結清單并輸出反轉後連結清單的頭節點。

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

參考題目一，我們可以寫出疊代+輔助棧的版本。首先周遊連結清單将節點存入輔助棧，然後再倒序周遊輔助棧并将每個節點的

next

指針指向前一個節點。

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     ListNode* reverseList(ListNode* head) {
12         if(head==nullptr || head->next==nullptr) return head;//如果頭結點為空或者隻有一個節點，傳回其本身
13         vector<ListNode*> aid;//輔助棧
14         while(head!=nullptr){//順序周遊連結清單并壓棧
15             aid.push_back(head);
16             head = head -> next;
17         }
18         ListNode* ans = new ListNode(0);//假頭節點
19         ListNode* temp = ans;
20         for(int i = aid.size()-1; i >= 0; --i){//倒序周遊節點并修改next指針
21             temp -> next = aid[i];
22             temp = temp -> next;
23         }
24         temp -> next = nullptr;
25         return ans->next;//傳回翻轉後的連結清單頭節點
26     }
27 };

O(m)

。

為連結清單長度，周遊連結清單和倒序周遊修改

next

指針各需要

O(m)

O(m)

解法二疊代+三指針

解法一的輔助棧耗費了大量空間，實際上隻需要使用三指針即可。我們使用指針

prePtr

，

curPtr

nextPtr

分别指向上一節點，目前節點，下一節點。初始時，

prePtr

curPtr

nextPtr

分别為

nullptr

head

以及

head->next

，然後順序周遊連結清單，将

curPtr

指向節點的

next

指針修改，使其指向

prePtr

指向的節點，之後更新三個指針，使其分别後移以為。周遊完成後，傳回目前

curPtr

即為答案。

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     ListNode* reverseList(ListNode* head) {
12         if(head==nullptr || head->next==nullptr) return head;//若頭結點為空或隻有一個節點，直接傳回其本身
13         ListNode* prePtr = nullptr;//上一節點
14         ListNode* curPtr = head;//目前節點
15         ListNode* nextPtr = head->next;//下一節點
16         while(nextPtr != nullptr){//依次周遊翻轉
17             curPtr -> next = prePtr;
18             prePtr = curPtr;
19             curPtr = nextPtr;
20             nextPtr = nextPtr -> next;
21         }
22         curPtr -> next = prePtr;
23         return curPtr;//傳回答案
24     }
25 };

O(m)

。周遊連結清單的時間消耗。

O(1)

。隻需常數個額外變量即可。

解法三遞歸

除此之外，我們還可以使用遞歸方法解決本題。一般來說遞歸的代碼比較簡潔，就是有的地方不容易想。這裡再提供遞歸版本代碼，供大家加深對遞歸的了解。

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     ListNode* reverseList(ListNode* head) {
12         if(head==nullptr) return head;
13         ListNode* temp = head -> next;
14         head -> next = ans;
15         ans = head;
16         reverseList(temp);
17         return ans;
18     }
19     ListNode* ans = nullptr;
20 };

O(m)

O(m)

題目三複雜連結清單的深拷貝

連結：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/

給你一個長度為

的連結清單，每個節點包含一個額外增加的随機指針

random

，該指針可以指向連結清單中的任何節點或空節點。

構造這個連結清單的深拷貝。深拷貝應該正好由

個全新節點組成，其中每個新節點的值都設為其對應的原節點的值。新節點的

next

指針和

random

指針也都應指向複制連結清單中的新節點，并使原連結清單和複制連結清單中的這些指針能夠表示相同的連結清單狀态。複制連結清單中的指針都不應指向原連結清單中的節點。

例如，如果原連結清單中有

和

兩個節點，其中

X.random-->Y

。那麼在複制連結清單中對應的兩個節點

，同樣有

x.random-->y

傳回複制連結清單的頭節點。

用一個由

個節點組成的連結清單來表示輸入/輸出中的連結清單。每個節點用一個

[val, random_index]

表示：

val：一個表示 Node.val 的整數
random_index：随機指針指向的節點索引（範圍從0到n-1）；如果不指向任何節點，則為null 你的代碼隻接受原連結清單的頭節點 head 作為傳入參數。

【Warrior刷題筆記】劍指offer 6 24 35. 三道題，讓你學會連結清單遞歸疊代輔助棧

輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例2

【Warrior刷題筆記】劍指offer 6 24 35. 三道題，讓你學會連結清單遞歸疊代輔助棧

輸入：head = [[1,1],[2,1]]
輸出：[[1,1],[2,1]]

示例 3：

【Warrior刷題筆記】劍指offer 6 24 35. 三道題，讓你學會連結清單遞歸疊代輔助棧

輸入：head = [[3,null],[3,0],[3,null]]
輸出：[[3,null],[3,0],[3,null]]

示例 4：

輸入：head = []
輸出：[]
解釋：給定的連結清單為空（空指針），是以傳回 null。

解法一暴力周遊

可以立馬想到的暴力方法就是周遊連結清單，使用雙指針對舊連結清單和新連結清單進行同步，先建立

random

指針指向全為空的新連結清單；然後對新連結清單的每個節點，使用上一步的雙指針同步方法再次周遊舊連結清單找到正确的

random

指向。

1 /*
  2 // Definition for a Node.
  3 class Node {
  4 public:
  5     int val;
  6     Node* next;
  7     Node* random;
  8     
  9     Node(int _val) {
 10         val = _val;
 11         next = NULL;
 12         random = NULL;
 13     }
 14 };
 15 */
 16 class Solution {
 17 public:
 18     Node* copyRandomList(Node* head) {
 19         if(head == NULL || head->next == NULL)//若頭結點為空或隻有頭結點
 20         {
 21             if(head == NULL)//如果頭結點為空
 22             {
 23                 return NULL;//則直接傳回頭結點
 24             }
 25             else//如果隻有頭結點
 26             {
 27                 Node* NewHead = new Node(0);//新連結清單的頭結點
 28                 NewHead->val = head -> val;//将頭結點進行複制
 29                 NewHead -> next = NULL;//因為隻有一個節點，next指向NULL
 30                 if(head -> random == head)
 31                 {
 32                     NewHead -> random = NewHead;
 33                 }
 34                 else
 35                 {
 36                     NewHead -> random = NULL;
 37                 }
 38                 return NewHead;
 39             }
 40         }
 41         else//如果不隻頭結點
 42         {
 43             vector<int> randomPosition;//建立一個數組，用于記憶各個節點random指針的指向節點，倆數字一組
 44                                        //例如1 31就代表第一個節點的random指向31節點，25 67就代表節點25
 45                                        //的random指向67節點
 46             Node* NewHead = new Node(0);//新連結清單的頭結點
 47             Node* Index = head;//采用雙指針技術，這個舊連結清單哨兵指向原連結清單的目前節點
 48             Node* newIndex = NewHead;//這個指針指向新連結清單的目前節點
 49             NewHead->val = head -> val;//将頭結點進行複制
 50             NewHead -> next = NULL;//因為隻有一個節點，next指向NULL
 51             NewHead -> random = NULL;//random節點之後統一修改，因為現在新連結清單還未成型
 52             Index = Index -> next;//頭結點複制完畢，舊連結清單哨兵向後位移指向下一個節點
 53             Node* positionOfRandom = NULL;//用來周遊舊連結清單确定random指向的遊标
 54             if(head -> random == NULL)//如果舊連結清單頭結點的random指向NULL
 55             {
 56                // NewHead -> random = NULL;//則新連結清單頭結點random也指向NULL
 57                 randomPosition.push_back(1);//1入數組，表示這是第一個節點
 58                 randomPosition.push_back(0);//0入數組，表示該節點的random指針指向null
 59             }
 60             else//如果頭節點random指向不為空，尋找頭結點random指向位置
 61             {
 62                 randomPosition.push_back(1);//1入數組，表示這是第一個節點
 63                 int flag = 1;//用來記錄random指向節點位置
 64                 positionOfRandom = head;//遊标指向頭節點
 65                 while(positionOfRandom != head -> random)//遊标持續移動直到找到random指向位置
 66                 {
 67                     flag++;
 68                     positionOfRandom = positionOfRandom -> next;
 69                 }
 70                 randomPosition.push_back(flag);//記錄位置的整數入數組
 71             }
 72             int count = 1;//記錄做到第幾個節點了
 73             while(Index != NULL)//每複制完一個節點舊連結清單哨兵向後位移一個節點，直到全部複制完畢
 74             {
 75 /***************進行節點複制工作************************************************/
 76                 count++;//處理的節點數+1
 77                 Node* temp = new Node(0);//建立一個節點
 78                 temp -> next = NULL;//先将next指向空
 79                 temp -> random = NULL;//先将random指向空
 80                 temp->val = Index->val;//将舊節點的值複制過來
 81                 newIndex->next = temp; //将建立節點鍊到新連結清單尾部
 82 
 83 /**************确定該節點random指向****************************************/
 84                 randomPosition.push_back(count);//count入數組，表示這是第count個節點
 85                 if(Index -> random == NULL)//如果舊連結清單該結點的random指向NULL
 86                {
 87                 randomPosition.push_back(0);//則用0記錄新連結清單該節點random也指向NULL
 88                }
 89             else//如果舊連結清單該節點random指向不為空，尋找該結點random指向位置
 90             {
 91                 int flag = 1;//用來記錄random指向節點位置
 92                 positionOfRandom = head;//遊标指向頭節點
 93                // Node* nonius = head -> random;
 94                 while(positionOfRandom != Index -> random)//遊标持續移動直到找到random指向位置
 95                 {
 96                     flag++;
 97                     positionOfRandom = positionOfRandom -> next;
 98                 }
 99                 randomPosition.push_back(flag);//記錄位置的整數入數組
100             }
101 
102                 Index = Index -> next;//處理完一個節點後倆遊标向後位移一個位置
103                 newIndex = newIndex -> next;                 
104             }
105 
106 /***********根據之前建立的輔助數組完成random指向工作*************************************/
107             //該步驟同樣采用雙哨兵技術
108             newIndex = NewHead;
109             for(int i = 0, j = 2; i < count; i++, j = j + 2)
110             {
111                 if(randomPosition[j-1] == 0)
112                 {
113                     newIndex -> random = NULL;
114                 }
115                 else
116                 {
117                     positionOfRandom = NewHead;
118                     for(int k = 0; k < randomPosition[j-1]-1; k++)
119                     {
120                         positionOfRandom = positionOfRandom -> next;
121                     }
122                  newIndex -> random = positionOfRandom;
123                 }
124                 newIndex = newIndex -> next;
125             }
126             return NewHead;
127         }
128     }
129 };

O(m²)

為連結清單長度，建新連結清單和修改

random

指針的時間消耗分别為

O(m)

O(m²)

O(1)

。隻需要常數個額外變量。

解法二遞歸+哈希表

對于普通連結清單的深拷貝，我們隻需要順次周遊然後建立對應節點就可以了。但本題的難點在于，我們建立一個節點并給

random

指針确定指向時，它應該指向的那個節點可能還不存在。于是我們可以在建立一個節點時，遞歸的建立他的後繼節點和

random

指針指向的節點。為了防止重複建立節點，我們使用哈希表标記該節點是否已有，如果有直接取用該節點，如果沒有，則建立它。

遞歸代碼通常比較簡潔，但是有的遞歸較難以了解，需要多加練習，多讀代碼，以加深了解。

1 /*
 2 // Definition for a Node.
 3 class Node {
 4 public:
 5     int val;
 6     Node* next;
 7     Node* random;
 8     
 9     Node(int _val) {
10         val = _val;
11         next = NULL;
12         random = NULL;
13     }
14 };
15 */
16 class Solution {
17 private:
18     unordered_map<Node*, Node*> created;//已建節點
19 public:
20     Node* copyRandomList(Node* head) {
21         if(head==nullptr) return head;//如果該節點為空，傳回其本身
22         if(!created.count(head)){//如果該節點未建立
23             Node* temp = new Node(head->val);//建立該節點
24             created[head] = temp;//标記該節點已建立
25             temp -> next = copyRandomList(head->next);//遞歸建立其後繼節點
26             temp -> random = copyRandomList(head->random);//遞歸建立其random指針指向的節點
27         }
28         return created[head];//傳回新連結清單
29     }
30 };

O(m)

。遞歸建立新連結清單的時間消耗。

O(m)

。哈希表的空間消耗。

解法三疊代 + 哈希表

除了遞歸+哈希外，本題還可以使用疊代+哈希的方式解決，該方法相較于上一方法更好了解。

與上一方法不同的是，我們隻關注目前節點

random

指針應指向的節點是否存在，并不關注目前節點的

random

指針應該指向的節點的

random

指針應指向的節點存不存在，也即不會直接遞歸建立一條鍊路上的全部節點（上一方法中，隻要

random

指針指向的節點不存在，就會遞歸建立。），如果不存在，建立之，并标記舊連結清單中對應節點的新節點已建立。

具體的，我們使用

pre

指針指向上一個節點，

cur

指針指向目前工作節點，初始時

pre

指向一個建立的假頭節點，

cur

指向舊連結清單頭節點。我們從頭節點開始依次周遊各個節點，首先查表判斷該節點是否已存在，如果已存在，直接取用之，将

pre

指針指向的節點的

next

指針指向已建立本節點，否則建立之。之後判斷其

random

指向是否為空或者已存在，已存在則調用之，不存在則建立之，并将本節點

random

指針指向它。最後更新

cur

指針指向本節點的下一節點繼續周遊。

1 ```cpp
 2 class Solution {
 3 private:
 4     unordered_map<Node*, Node*> created;
 5 public:
 6     Node* copyRandomList(Node* head) {
 7         if(head==nullptr) return head;//如果頭結點為空，傳回其本身
 8         Node* pre = new Node(0);//假頭節點，用于避免邊界判斷帶來的麻煩
 9         Node* cur = head;//目前指針指向頭節點
10         while(cur!=nullptr){//依次周遊連結清單各節點，同時構造新連結清單
11             if(!created.count(cur)){//如果目前指針指向的舊連結清單節點未被建立（其有可能在之前的節點完善random指針時被建立）
12                 created[cur] = new Node(cur->val);//則建立之
13             }//如果已被建立則直接使用之
14             pre -> next = created[cur];//将前一節點的next指針指向本節點
15             pre = pre -> next;//更新pre指針指向本節點
16             if(cur->random == nullptr) created[cur] -> random = nullptr;//若該節點的random指針指向空，則新連結清單中的也指向空
17             else{//否則完善其random指針指向
18                 if(!created.count(cur->random)){//如果其random應指向的節點還未建立
19                     created[cur->random] = new Node(cur->random->val);//則建立之
20                 }//并将random指針指向他
21                 created[cur]->random = created[cur->random];
22             }
23             cur = cur -> next;//更新目前工作指針指向本節點的下一節點
24         }
25         return created[head];//傳回答案
26     }
27 };

O(m)

。周遊一次連結清單的時間消耗

O(m)

解法四疊代

在上述方法中，因為使用了哈希表，是以空間複雜度比較高。這裡有另外的一種方法，可以實作

O(1)

空間複雜度。

具體的，我們首先周遊一遍舊連結清單，并建立複制節點，注意，這次我們将建立的節點直接連結在原節點的後邊，同時保持連結清單的完整性。

例如對于連結清單

A→B→C

，我們可以将其拆分為

A → A′→ B → B′→ C → C′

。對于任意一個原節點

，其拷貝節點

S'

即為其後繼節點。

通過這樣的方式，我們很容易就能找到新節點的

random

節點所指向的正确節點，因為他們就是舊連結清單中原節點中

random

指針指向節點的後繼結點或者空節點，通過一次周遊我們就能完善所有節點的

random

指針。最後，再通過一次周遊将兩個連結清單斷開，即可完成深拷貝操作。注意，原連結清單也必須還原，不然無法通過。

1 class Solution {
 2 public:
 3     Node* copyRandomList(Node* head) {
 4         if(!head) return head;//如果頭結點為空，傳回其本身
 5 
 6         //第一次周遊，将拷貝節點連結到原節點之後，使其成為原節點的後繼結點
 7         Node* temp = head;
 8         while(temp!=nullptr){
 9             Node* newNode = new Node(temp->val);
10             newNode -> next = temp -> next;
11             newNode -> random = temp -> random;
12             temp -> next = newNode;
13             temp = newNode -> next;
14         }
15 
16         //第二次周遊，完善各拷貝節點的random指向
17         temp = head;
18         Node* ans = head -> next;
19         while(temp!=nullptr){
20             if(temp->next->random != nullptr){
21                 temp->next->random = temp->next->random->next;
22             } 
23             temp = temp -> next -> next;
24         }
25 
26         //第三次周遊，将新舊連結清單斷鍊并恢複原連結清單
27         temp = head;
28         while(temp!=nullptr){
29             Node* copy = temp -> next -> next;
30             if(!copy) break;
31             temp -> next -> next = copy -> next;
32             temp -> next = copy;
33             temp = copy;
34         }
35         temp -> next = nullptr;
36         return ans;
37     }
38 };

O(m)

O(1)

。隻需常數個額外變量。

Tips：

在上面的分析中可以看到，對于涉及連結清單的，包含增删等操作時，使用假頭/尾節點可以避免很多邊界判斷帶來的麻煩。這一點可以在解題過程中多加應用。

更多知識内容分享：

力扣個人首頁https://leetcode-cn.com/profile/articles/

CSDN個人首頁https://blog.csdn.net/qq_39255924

牛客個人首頁https://blog.nowcoder.net/newcoderthewarrior

【Warrior刷題筆記】劍指offer 6 24 35. 三道題，讓你學會連結清單遞歸疊代輔助棧

【Warrior刷題筆記】劍指offer 6 24 35. 三道題，讓你學會連結清單遞歸疊代輔助棧

題目一從尾到頭列印連結清單

1.描述

2.示例

解法一疊代+輔助棧

解題思路

代碼

複雜度分析

解法二遞歸

題目二反轉連結清單

解法二疊代+三指針

解法三遞歸

題目三複雜連結清單的深拷貝

解法一暴力周遊

解法二遞歸+哈希表

解法三疊代 + 哈希表

解法四疊代

Tips：

繼續閱讀

swmm與lisflood-fp源碼如何一起編譯 CMake指令

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

hdu7108哈希

【Warrior刷題筆記】劍指offer 6 24 35. 三道題，讓你學會連結清單遞歸疊代輔助棧

題目一 從尾到頭列印連結清單

1.描述

2.示例

解法一 疊代+輔助棧

解題思路

代碼

複雜度分析

解法二 遞歸

題目二 反轉連結清單

解法二 疊代+三指針

解法三 遞歸

題目三 複雜連結清單的深拷貝

解法一 暴力周遊

解法二 遞歸+哈希表

解法三 疊代 + 哈希表

解法四 疊代

Tips：

繼續閱讀

題目一從尾到頭列印連結清單

解法一疊代+輔助棧

解法二遞歸

題目二反轉連結清單

解法二疊代+三指針

解法三遞歸

題目三複雜連結清單的深拷貝

解法一暴力周遊

解法二遞歸+哈希表

解法三疊代 + 哈希表

解法四疊代