这道题和leetcode133-克隆图有异曲同工之妙。
原题
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的深拷贝。
示例：
输入:
{“id”:”1”,”next”:{“id”:”2”,”next”:null,”random”:{“ref”:”2”},”val”:2},”random”:{“ref”:”2”},”val”:1}解释:
节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。
节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。
提示:
- 你必须返回给定头的拷贝作为对克隆列表的引用。
解法
思想
和leetcode133-克隆图的解法一致，甚至只需要改几行代码。
代码
/*
// Definition for a Node.
class Node {
public int val;
public Node next;
public Node random;
public Node() {}
public Node(int _val,Node _next,Node _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
//hashmap维持原链表和克隆链表之间节点的对应关系
Map<Node, Node> lookup;
public Node copyRandomList(Node head) {
lookup = new HashMap<>();
return dfs(head);
}
private Node dfs(Node node) {
if (node == null) return null;
//存在对应的克隆节点直接返回
if (lookup.containsKey(node)) return lookup.get(node);
//先创建对应的克隆节点，next和random在递归返回的时候添加。
Node clone = new Node(node.val,null,null);
lookup.put(node, clone);
clone.next = dfs(node.next);
clone.random = dfs(node.random);
return clone;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode138-%e5%a4%8d%e5%88%b6%e5%b8%a6%e9%9a%8f%e6%9c%ba%e6%8c%87%e9%92%88%e7%9a%84%e9%93%be%e8%a1%a8/
相关推荐
-
leetcode1111-有效括号的嵌套深度
原题 有效括号字符串 仅由 "(" 和 ")" 构成，并符合下述几个条件之一： 空字符串 连接，可以记作 AB（A 与 B 连接），其中 A 和 B 都是有效括号字符串 嵌套，可以...
-
leetcode47-全排列II
原题 给定一个可包含重复数字的序列，返回所有不重复的全排列。 示例: 输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ] 解法 思想 这道题...
-
力扣杯春季个人赛-剧情触发时间
这次的个人赛真是让我认清了自己的实力。。两道困难题都没做出?，虽然大家的通过率也不咋地。。 最后排名 我记录一道做出来的题吧，这道题是一道中等题，通过率如下，虽然题目不难，但由于时...
-
leetcode154-寻找旋转排序数组中的最小值II
原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。...
-
leetcode429-N叉树的层序遍历
原题 给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。 例如，给定一个 3叉树 : 返回其层序遍历: [ [1], [3,2,4], [5,6] ] 说明:...
-
leetcode945-使数组唯一的最小增量
原题 给定整数数组 A，每次 move 操作将会选择任意 A[i]，并将其递增 1。 返回使 A 中的每个值都是唯一的最少操作次数。 示例 1: 输入： [1,2,2] 输出： 1...
-
leetcode876-链表的中间结点
原题 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。 示例 1: 输入： [1,2,3,4,5] 输出： 此列表中的结...
-
leetcode378-有序矩阵中第K小的元素
原题 给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。请注意，它是排序后的第k小元素，而不是第k个元素。 示例: matrix = [ &nbs...
-
leetcode779-第K个语法符号
原题 在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。 给定行数 N 和序数 K，返回第 N 行中第 K个字符。（K从1开始） 例子： 输入: N...
-
leetcode494-目标和
原题 给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。...