剑指Offer35- - 链表

1. 题目描述

这题题意感觉说的不是很清楚，容易让人产生歧义！其实题意很简单，给你一个链表 head，你深拷贝它，然后返回即可，注意不能修改原链表

/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*/

2. 坑

首先，这题绝对没你看上去的那么简单，复制链表？太简单了，不就是链表的创建吗？
不！本题有一个有意思的地方，就是它有一个随机指针，随机指针以为着什么？
意味着，它指向的节点，可能还未创建！
因此说，我们不能直接遍历链表，来创建新链表，需要一些特殊方法

3. 思路1 – 哈希表

$O(N)$时间， $O(N)$空间

思路呢，也很简单，既然随机指针可能指向一个还未创建的节点，那么我们就先创建它，然后通过哈希表存起来，并与原链表的相应节点做映射。
这样，当我们下次遍历到这个随机节点时，我们可以检查一下哈希表，看看是否已经建立过了，避免重复创建节点。

代码

// 本题的难点主要在于，当我们需要将指针指向某个节点时
// 随机指针指向的节点可能还不存在
class Solution {
public:Node* copyRandomList(Node* head) {if(head == nullptr) return nullptr;Node *dummy = new Node(-1);Node *cur = dummy;// refto 存储的是，原链表head与它的拷贝之间的映射unordered_map<Node*, Node*> refto;while(head) { // 遍历原链表的每一个节点，创建它自己和他的random指针指向的节点// 并让它的random指针指向原链表random指针指向的节点if(refto[head] == nullptr) {Node *newNode = new Node(head->val);refto[head] = newNode;}if(head->random && refto[head->random] == nullptr) {Node *newNode = new Node(head->random->val);refto[head->random] = newNode;}refto[head]->random = refto[head->random];cur->next = refto[head];cur = refto[head];head = head->next;}return dummy->next;}
};

4. 思路2 – 原地修改

$O(N)$ 时间， $O(1)$空间。

参考题解，最后的动图很易懂！
注意在计算空间复杂度时，是不考虑创建新链表产生的空间的，因为那是必须的，我们主要考虑的时额外空间的复杂度。

大体思路，只要看了题解中的动图演示，基本就了解了，这里主要阐述一下流程：

1. 遍历原链表，对于链表中的每个节点 $node$，在它的后面新创建一个新节点 $newNode$并插入到链表当中，即 $node$ ➡️ $newNode$ ➡️ $node$->$next$，这个 $newNode$ 就是对 $node$ 的深拷贝。（这一步就是核心所在，直接在原链表的基础上创建新链表，然后再把它分离出来，太妙了！！）
2. 修改 $newNode$ 的 $random$ 指针。
3. 创建新链表的头，修改 $newNode$ 的 $next$。

代码

class Solution {
public:Node* copyRandomList(Node* head) {if(head == nullptr) return nullptr;// 原地拷贝for(Node *node = head; node != nullptr; node = node->next->next) {Node *newNode = new Node(node->val);// node -> newNode -> node.nextnewNode->next = node->next;node->next = newNode;}// 修改random指针for(Node *node = head; node != nullptr; node = node->next->next) {Node *newNode = node->next;// 判断下randodm是否存在，存在的话，才有我们的copy// 注意要指向node->random->next而不是node->random// 因为node->random->next是我们自己创建的newNode->random = (node->random != nullptr) ? node->random->next : nullptr;}// 修改next指针以分离我们创建的链表Node *newHead = head->next;for(Node *node = head; node != nullptr; node = node->next) {Node *newNode = node->next;node->next = newNode->next; // 恢复原链表的next指针// 判断下一个节点是否存在，存在的话，才有我们的copynewNode->next = (newNode->next != nullptr) ? newNode->next->next : nullptr; // 修改我们创建的链表的指针}return newHead;}
};