X

LEETCODE 138. Copy List with Random Pointer 解题思路分析

复制带随机指针的链表

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

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

我们用一个由 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-解题思路分析/
Categories: leetcode
kwantong:

View Comments (0)