wordpress站点搭建/香蕉和忘忧草对焦虑的影响

1. 问题描述

2. 样例说明

3. 解法一：哈希表

3.1 算法思想

(1)我们先不考虑结点的random指针，先通过next指针把链表连接起来。创建一个表头结点，然后遍历题目给定的链表，创建新结点，不断与上一结点连接，产生一个新的链表。

(2) 在第(1)步的过程中，通过哈希表建立映射关系，采用的是unordered_map结构。让原链表的结点与我们创建的新链表的结点一一对应，方便我们处理random指针。在处理random指针时，遍历哈希表，将随机指针指向对应的位置。

3.2 代码

/*
struct RandomListNode {int label;struct RandomListNode *next, *random;RandomListNode(int x) :label(x), next(NULL), random(NULL) {}
};
*/
class Solution {
public:RandomListNode* Clone(RandomListNode* pHead) {if(pHead==nullptr)  return nullptr;RandomListNode *dummy=new RandomListNode(0);  //表头结点RandomListNode *pre=dummy, *cur=pHead;unordered_map<RandomListNode*,RandomListNode*> map;  //创建哈希表while(cur){RandomListNode *clone=new RandomListNode(cur->label);  //拷贝结点pre->next=clone;  //连接map[cur]=clone;  //建立映射关系pre=pre->next;cur=cur->next;}for(auto&[key,value]:map){  //遍历哈希表value->random=key->random==nullptr?nullptr:map[key->random];}delete dummy;  //释放new的空间return map[pHead];}
};

3.3 时间空间复杂度分析

时间复杂度：O(n), 遍历一次链表和哈希表的时间
空间复杂度：O(n), 哈希表使用的空间

4. 解法二：链表拼接、拆分

4.1 算法思想

4.2 代码

class Solution {
public:RandomListNode* Clone(RandomListNode* pHead) {if(!pHead) return pHead;    // 为空则返回RandomListNode* cur = pHead;while(cur){RandomListNode* tmp = new RandomListNode(cur->label);    // 拷贝节点tmp->next = cur->next;cur->next = tmp;cur = tmp->next;}RandomListNode *old = pHead, *clone = pHead->next, *ret = pHead->next;while(old){clone->random = old->random == NULL ? NULL : old->random->next;    // 处理拷贝节点的随机指针if(old->next) old = old->next->next;    // 注意特判空指针if(clone->next) clone = clone->next->next;}old = pHead, clone = pHead->next;while(old){    // 拆分链表if(old->next) old->next = old->next->next;if(clone->next) clone->next = clone->next->next;old = old->next;clone = clone->next;}return ret;}
};

4.3 时间空间复杂度分析

时间复杂度：O(n), 遍历了三次链表
空间复杂度：O(1), 使用了常数个链表指针变量