剑指 Offer 35. 复杂链表的复制

示例1:
碎碎念
解析
碎碎想
如何递归
代码
不妨再大胆一些？
碎碎话

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例1:

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

篇幅有限，这里只给出一个示例。

碎碎念

现在时间是2022年的5月6号，在此年的3月28号我写过了这题。但今天看到这题我又忘记该怎么写了，说到底还是学得不够透。所以借着这个机会深度总结一下。

解析

如果不知道题目的意思。我应该可以进一步解释，我明白，链表的指向（这里指next、random）都是指针，也就是一个对象的引用，所以，我不可以简单的进行一个赋值操作，因为对于一个引用，赋值仅仅是传递了一个内存地址，用试图用原先的指针赋值给一个新指针，那么此时新指针指向的依然还是原对象，也就是说，这样的拷贝操作是毫无作用的。

所以，简单来说，题目需要我复刻它给出的指针，它需要一个值与原链表相同，但是内存地址与原链表完全不同的链表结构，也就是进行一次链表的深拷贝。

看到这题，我的第一反映就是递归。这个应该很容易联想。以示例1为例，如果我需要复刻结点7那么我们就需要复刻7指向的next和random，同理，如果要复刻7的next，那么就需要复刻7的next的next，7的next的random…很显然，发现了这就是个套娃，所以这就很适合递归，nice。可是，我该怎么递归，我在这里迷失了。

碎碎想

其实，我可以把这题的链表想象成是一个颗二叉树。next、random就看作是其的左右结点。

因为，做了这么多题，看了这么多的题解与指南，我已知道，在图论中，图结构本身其实也是树结构，它只不过是一颗N叉树。所以代入此题，我不用在意这个random随机指向，它的随机完全没有问题，是合理的。所以，我应该怎么递归呢。

如何递归

设计递归-这个递归需要干什么事？

我希望当我传入一个链表结点后，它能够将链表进行一次深拷贝，并将深拷贝后的新结点返回给我。

举个例子，假设有单链表7->13->11->null，如图

DFC2850DF3C5D15432E9CF490884CAE9

终止条件是什么

首先，提到递归，我应该本能的想到需要有一个base case，也就是需要有一个终止递归的条件，告诉它，这条路已经走到头了，不要无休止的陷入递归。stackoverflow警告⚠️

那么这个base case是什么呢？这个也很容易想到，当传入的链表结点为null时，这条分支路径就递归到头了，那么我们返回的也应该是null *(在C/C++中为nullptr or NULL)*，这个应该很好理解。

我的武器在哪里？

那么之后我还要做什么，对于每一次深拷贝后的结点，我需要有个东西对它进行储存，否则我无法拿到random指向的深拷贝（如果在此之前我拷贝过相同结点的话）。

所以，我需要有这样的结构，给予一个原先的结点，它能够得到对它进行深拷贝后的结点（如果深拷贝结点已经存在的情况话）

显然，哈希表对这样的一一映射关系的存储效率得天独厚。

所以，我需要有一个unordered_map<Node*, Node*> map，我需要用它来干这件大事。

具体？

当哈希表发现中如果已经存在原结点的新结点，我只需要返回这个新结点就可以了。

如果没有发现呢？那么我就需要Node* node = new Node(val)，这个val是原结点的head->val，node就是我们的新结点。那，新结点的next、random呢？我只需要将原结点的next、random传入我们设计这个递归函数中，其它的，全权不需要我操心了。之后返回这个结点就算完成了。

代码

class Solution {
public:
    unordered_map<Node*, Node*> map;
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;
        if (map.count(head)) return map[head];
        Node* node = new Node(head->val);
        map[head] = node;
        node->next = copyRandomList(head->next);
        node->random = copyRandomList(head->random);
        return node;
    }
};

可能有些疑问，为什么是先map[head] = node;之后再赋值node的next与random呢？

先想想如果按照先赋值全部以后再将其添加的哈希表中会发生什么，答案是stackoverflow，无限递归了，这是为什么呢？如果脑中浅浅的执行一下你会发现，一旦遇上循环指针，我们也许在map中永远找不到node了，终止条件覆盖不到这种情况，它会一直递归下去的。

那为什么按代码里的顺序就可以呢？它怎么解决上述的问题？

原因是我们Node* node = new Node(head->val);在生成新结点后就进行了map[head] = node;将新结点存储到哈希表的操作。之后再针对原指针的next、random进行递归，即便遇上循环指针，它也会触发if (map.count(head)) return map[head];返回了我们创建的新结点，也就终止了递归操作。

而当新的结点返回，我们就可以顺利将node->next和node->random进行赋值操作了。

最终，所有递归调用栈弹出，返回的自然是最初的node，恰到好处。

不妨再大胆一些？

其实，对于初入编程的学习者来说，递归其实是一个比较难懂的概念，知其然却不知其所以然，至少对于我来说是这样的。这样的情况持续了相当长一段时间，一入递归深似海，从此offer为路人。其实对于递归这个概念，我并没有什么特别的好的技巧，但是经过很长一段时间的刷题思考，或是知觉使然，也逐渐有了一些经验。

经验告诉我，在学习递归时，很容易陷入递归的调用栈中挣扎，这太正常了，我们的脑袋可压不了几个调用栈。所幸，它应该总可以描述成我们可以翻译的树形结构，我们都知道程序代码是顺序执行的，所以完全可以拿起手中的草稿纸对这个调用顺序一探究竟，倒要看看它凭什么就能如此简约的解决这样的问题，但写这样的执行顺序是一定不要忘记使用缩进或其它辨别方式来表示递归的分支，否则，草稿纸一样无法拯救一个试图变强的灵魂。