関小君刷题记

复制带随机指针的链表

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的 深拷贝。

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。

示例 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。

提示：

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=138

解题思路分析：

本题与 LEETCODE 1485. Clone Binary Tree With Random Pointer 解题思路分析 几乎是如出一辙，唯一的区别在于本题的核心是链表，而LEETCODE 1485是二叉树，除此之外在题目的描述以及解题思路上完全没有区别，强烈建议首先参考LEETCODE 1485这篇文章，然后再使用本题来练手比较好。

实现代码：

Map<Node, Node> map=new HashMap<>();
public Node copyRandomList(Node head) {
    return copy(head);
}

Node copy(Node head){
    if(head==null) return null;
    if(map.containsKey(head)) return map.get(head);
    Node copy=new Node(head.val);
    map.put(head,copy);
    copy.next=copy(head.next);
    copy.random=copy(head.random);
    return copy;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 16.23% of Java online submissions for Copy List with Random Pointer.

Memory Usage: 43.2 MB, less than 5.06% of Java online submissions for Copy List with Random Pointer.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-138-copy-list-with-random-pointer-解题思路分析/