原文链接: https://leetcode-cn.com/problems/copy-list-with-random-pointer
英文原文
A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.
Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.
For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.
Return the head of the copied linked list.
The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
val: an integer representingNode.valrandom_index: the index of the node (range from0ton-1) that therandompointer points to, ornullif it does not point to any node.
Your code will only be given the head of the original linked list.
Example 1:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Example 2:
Input: head = [[1,1],[2,1]] Output: [[1,1],[2,1]]
Example 3:
Input: head = [[3,null],[3,0],[3,null]] Output: [[3,null],[3,0],[3,null]]
Example 4:
Input: head = [] Output: [] Explanation: The given linked list is empty (null pointer), so return null.
Constraints:
0 <= n <= 1000-10000 <= Node.val <= 10000Node.randomisnullor is pointing to some node in the linked list.
中文题目
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示Node.val的整数。random_index：随机指针指向的节点索引（范围从0到n-1）；如果不指向任何节点，则为null。
你的代码 只 接受原链表的头节点 head 作为传入参数。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]
示例 4：
输入：head = [] 输出：[] 解释：给定的链表为空（空指针），因此返回 null。
提示：
0 <= n <= 1000-10000 <= Node.val <= 10000Node.random为空（null）或指向链表中的节点。
通过代码
高赞题解
解法一
这题的最大难点就在于复制随机指针，比如下图中
节点1的随机指针指向节点3
节点3的随机指针指向节点2
节点2的随机指针指向空
我们可以用三步走来搞定这个问题
第一步，根据遍历到的原节点创建对应的新节点，每个新创建的节点是在原节点后面，比如下图中原节点1不再指向原原节点2，而是指向新节点1
第二步是最关键的一步，用来设置新链表的随机指针
上图中，我们可以观察到这么一个规律
原节点1的随机指针指向原节点3，新节点1的随机指针指向的是原节点3的next
原节点3的随机指针指向原节点2，新节点3的随机指针指向的是原节点2的next
也就是，原节点i的随机指针(如果有的话)，指向的是原节点j
那么新节点i的随机指针，指向的是原节点j的next
第三步就简单了，只要将两个链表分离开，再返回新链表就可以了
代码实现:
[]class Solution { public Node copyRandomList(Node head) { if(head==null) { return null; } Node p = head; //第一步，在每个原节点后面创建一个新节点 //1->1'->2->2'->3->3' while(p!=null) { Node newNode = new Node(p.val); newNode.next = p.next; p.next = newNode; p = newNode.next; } p = head; //第二步，设置新节点的随机节点 while(p!=null) { if(p.random!=null) { p.next.random = p.random.next; } p = p.next.next; } Node dummy = new Node(-1); p = head; Node cur = dummy; //第三步，将两个链表分离 while(p!=null) { cur.next = p.next; cur = cur.next; p.next = cur.next; p = p.next; } return dummy.next; } }
[]class Solution(object): def copyRandomList(self, head): if not head: return None p = head # 第一步，在每个原节点后面创建一个新节点 # 1->1'->2->2'->3->3' while p: new_node = Node(p.val,None,None) new_node.next = p.next p.next = new_node p = new_node.next p = head # 第二步，设置新节点的随机节点 while p: if p.random: p.next.random = p.random.next p = p.next.next # 第三步，将两个链表分离 p = head dummy = Node(-1,None,None) cur = dummy while p: cur.next = p.next cur = cur.next p.next = cur.next p = p.next return dummy.next
解法二
我们用哈希表来解决这个问题
首先创建一个哈希表，再遍历原链表，遍历的同时再不断创建新节点
我们将原节点作为key，新节点作为value放入哈希表中
第二步我们再遍历原链表，这次我们要将新链表的next和random指针给设置上
从上图中我们可以发现，原节点和新节点是一一对应的关系，所以
map.get(原节点)，得到的就是对应的新节点
map.get(原节点.next)，得到的就是对应的新节点.next
map.get(原节点.random)，得到的就是对应的新节点.random
所以，我们只需要再次遍历原链表，然后设置：
新节点.next -> map.get(原节点.next)
新节点.random -> map.get(原节点.random)
这样新链表的next和random都被串联起来了
最后，我们然后map.get(head)，也就是对应的新链表的头节点，就可以解决此问题了。
代码实现:
[]class Solution { public Node copyRandomList(Node head) { if(head==null) { return null; } //创建一个哈希表，key是原节点，value是新节点 Map<Node,Node> map = new HashMap<Node,Node>(); Node p = head; //将原节点和新节点放入哈希表中 while(p!=null) { Node newNode = new Node(p.val); map.put(p,newNode); p = p.next; } p = head; //遍历原链表，设置新节点的next和random while(p!=null) { Node newNode = map.get(p); //p是原节点，map.get(p)是对应的新节点，p.next是原节点的下一个 //map.get(p.next)是原节点下一个对应的新节点 if(p.next!=null) { newNode.next = map.get(p.next); } //p.random是原节点随机指向 //map.get(p.random)是原节点随机指向 对应的新节点 if(p.random!=null) { newNode.random = map.get(p.random); } p = p.next; } //返回头结点，即原节点对应的value(新节点) return map.get(head); } }
[]class Solution(object): def copyRandomList(self, head): if not head: return None # 创建一个哈希表，key是原节点，value是新节点 d = dict() p = head # 将原节点和新节点放入哈希表中 while p: new_node = Node(p.val,None,None) d[p] = new_node p = p.next p = head # 遍历原链表，设置新节点的next和random while p: # p是原节点，d[p]是对应的新节点，p.next是原节点的下一个 # d[p.next]是原节点下一个对应的新节点 if p.next: d[p].next = d[p.next] # p.random是原节点随机指向 # d[p.random]是原节点随机指向 对应的新节点 if p.random: d[p].random = d[p.random] p = p.next # 返回头结点，即原节点对应的value(新节点) return d[head]
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 120400 | 181939 | 66.2% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
相似题目
| 题目 | 难度 |
|---|---|
| 克隆图 | 中等 |
