题目描述（中等难度）

给一个链表，返回复制后的链表。链表节点相对于普通的多了一个 指针，会随机指向链表内的任意节点或者指向 null。

思路分析

这道题其实和 133 题 复制一个图很类似，这里的话就是要解决的问题就是，当更新当前节点的 random 指针的时候，如果 random 指向的是很后边的节点，但此时后边的节点还没有生成，那么我们该如何处理。

和 一样，我们可以利用 HashMap 将节点提前生成并且保存起来，第二次遍历到他的时候直接从 HashMap 里边拿即可。

这里的话就有两种思路，一种需要遍历两边链表，一种只需要遍历一遍。

解法一

首先利用 来一个不用思考的代码。

遍历第一遍链表，我们不考虑链表之间的相互关系，仅仅生成所有节点，然后把它存到 HashMap 中，val 作为 key，Node 作为 value。

遍历第二遍链表，将之前生成的节点取出来，更新它们的 next 和 random 指针。

解法二

核心思想就是延迟更新它的 next。

看下代码理解一下含义吧

解法三

上边的两种解法都用到了 HashMap ，所以额外需要 O(n) 的空间复杂度。现在考虑不需要额外空间的方法。

主要参考了这里-and-linear-time-complexity-O(N))。主要解决的问题就是我们生成节点以后，当更新它的 的时候，怎么找到之前生成的节点，前两种解法用了 HashMap 全部存起来，这里的话可以利用原来的链表的指针域。

主要需要三步。

1. 生成所有的节点，并且分别插入到原有节点的后边
2. 将新旧节点分离开来

一图胜千言，大家看一下下边的图吧。

代码对应如下。

解法四

解法三利用原链表的 next 域把新生成的节点保存了起来。类似的，我们还可以利用原链表的 random 域把新生成的节点保存起来。

主要还是三个步骤。

1. 生成所有的节点，将它们保存到原链表的 random 域，同时利用新生成的节点的 next 域保存原链表的 random。
2. 更新新生成节点的 random 指针。

一图胜千言。

相应的代码如下。

总

解法一、解法二是比较直接的想法，直接利用 存储之前的节点。解法三、解法四利用原有链表的指针，通过指来指去完成了赋值。链表操作的核心思想就是，在改变某一个节点的指针域的时候，一定要把该节点的指针指向的节点用另一个指针保存起来，以免造成丢失。

添加好友一起进步~

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 查看详情