【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
