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

额，这篇文章是昨天的头条文章，但由于自己起了一个骚的题目，导致翻车严重，没几个人看，所以起个正常的标题 再发一次。

囧

一、题目描述

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

示例 1：

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

提示：

• -10000 <= Node.val <= 10000
• Node.random 为空（null）或指向链表中的节点。
• 节点数目不超过 1000 。

二、题目解析

我们依旧用 四步分析法 进行结构化的分析。

• 模拟：模拟题目的运行。
• 规律：尝试总结出题目的一般规律和特点。
• 匹配：找到符合这些特点的数据结构与算法。
• 边界：考虑特殊情况。

1、模拟

对于链表中的每个节点来说，它都有三个特征：

• 值为 val
• 一个指向下一个节点的指针 next
• 一个指向随机节点的指针 random

要想 复制这样一个复杂链表 必须要考虑到这三个特征。

如果没有 random 指针的话，那就是普通的链表，只需要遍历链表，然后每轮创建新节点，同时赋值 val 和调整前驱指针指向当前节点就行。

这题出现了 random 指针，由于它可以指向 null 、前面的节点或者后面的节点， 无法做到在一次遍历的过程中就确定下来，因为如果是 指向后面的节点 ，但后面的节点还没有创建生成，无法确定。

所以，我们需要在 一开始把所有的节点都创建出来 ，避免 random 找不到指向，同时观察上图， 每个节点都通过 random 对应着一个新的节点 ，这种一一对应的关系，符合 哈希表 的特征。

此时的哈希表 以原链表的节点作为键，新创建的节点作为值 。

原链表（Key）中的每个节点都有 next 和 random 指针，而新链表（Value） 没有 next 和 random 指针。

需要通过第二次的遍历过程进行指针指向的调整。

在第二次遍历过程中，以原链表中的节点作为键，查找当前 原节点 的指针指向，然后调整 新节点 的指针指向。

2、规律

无

3、匹配

数据结构为链表，遍历方式使用 while 的方式。

4、边界

• 链表为空

三、动画描述

四、图片描述