【Warrior刷題筆記】劍指offer 6 24 35. 三道題，讓你學會鏈表遞歸迭代輔助棧
題目一 從尾到頭列印鏈表
來源：力扣（LeetCode）
鏈接：//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)。遞歸的空間消耗。
題目二 反轉鏈表
來源：力扣（LeetCode）
鏈接：//leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
1.描述
定義一個函數，輸入一個鏈表的頭節點，反轉該鏈表並輸出反轉後鏈表的頭節點。
2.示例
- 示例 1：
輸入: 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)。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)。遞歸的空間消耗。
題目三 複雜鏈表的深拷貝
來源：力扣（LeetCode）
鏈接：//leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/
1.描述
給你一個長度為n的鏈表，每個節點包含一個額外增加的隨機指針random，該指針可以指向鏈表中的任何節點或空節點。
構造這個鏈表的深拷貝。 深拷貝應該正好由n個全新節點組成，其中每個新節點的值都設為其對應的原節點的值。新節點的next指針和random指針也都應指向複製鏈表中的新節點，並使原鏈表和複製鏈表中的這些指針能夠表示相同的鏈表狀態。複製鏈表中的指針都不應指向原鏈表中的節點。
例如，如果原鏈表中有X和Y兩個節點，其中X.random-->Y。那麼在複製鏈表中對應的兩個節點x和y，同樣有x.random-->y。
返回複製鏈表的頭節點。
用一個由n個節點組成的鏈表來表示輸入/輸出中的鏈表。每個節點用一個[val, random_index]表示：
val：一個表示 Node.val 的整數。random_index：隨機指針指向的節點索引（範圍從0到n-1）；如果不指向任何節點，則為null。
你的程式碼只接受原鏈表的頭節點head作為傳入參數。
2.示例
- 示例 1：
輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
- 示例2
輸入：head = [[1,1],[2,1]]
輸出：[[1,1],[2,1]]
- 示例 3：
輸入：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²)。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，其拷貝節點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：
在上面的分析中可以看到，對於涉及鏈表的，包含增刪等操作時，使用假頭/尾節點可以避免很多邊界判斷帶來的麻煩。這一點可以在解題過程中多加應用。
更多知識內容分享：
力扣個人主頁//leetcode-cn.com/profile/articles/
CSDN個人主頁//blog.csdn.net/qq_39255924
牛客個人主頁//blog.nowcoder.net/newcoderthewarrior
