leetcode138-复制带随机指针的链表

这道题和leetcode133-克隆图有异曲同工之妙。

原题

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

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

示例:

leetcode138-复制带随机指针的链表

输入:
{“$id”:”1”,”next”:{“$id”:”2”,”next”:null,”random”:{“$ref”:”2”},”val”:2},”random”:{“$ref”:”2”},”val”:1}

解释:
节点 1 的值是 1,它的下一个指针和随机指针都指向节点 2 。
节点 2 的值是 2,它的下一个指针指向 null,随机指针指向它自己。

提示:

  1. 你必须返回给定头的拷贝作为对克隆列表的引用。

解法

思想

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/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年12月16日
下一篇 2019年12月18日

相关推荐

  • leetcode33-搜索旋转排序数组

    原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值,…

    算法 2020年1月1日
    0150
  • leetcode295-数据流的中位数

    原题 中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。 例如, [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.…

    算法 2020年2月12日
    090
  • leetcode206-反转链表

    原题 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法…

    2019年12月16日
    0150
  • leetcode705-设计哈希集合

    原题 不使用任何内建的哈希表库设计一个哈希集合 具体地说,你的设计应该包含以下的功能 add(value):向哈希集合中插入一个值。 contains(value) :返回哈希集合…

    算法 2019年12月18日
    0140
  • leetcode36-有效的数独

    原题 判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-…

    2019年12月26日
    090
  • 十大排序算法与Java实现

    本文参考资源: https://github.com/iTimeTraveler/SortAlgorithms 十大经典排序算法 - 冰狼爱魔 - 博客园 十大经典排序算法总结(J…

    2020年3月11日
    0780
  • leetcode328-奇偶链表

    原题 给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空…

    算法 2019年12月16日
    0130
  • leetcode215-数组中的第K个最大元素

    原题 在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 示例1: 输入: [3,2,1,5,6,4] 和…

    算法 2020年2月10日
    0140
  • 蓝桥杯试题-大小写转换

    原题 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述   输入一个字符串,将大写字符变成小写、小写变成大写,然后输出 输入格式 acbAB 输出格式 ACBab …

    算法 2020年2月29日
    060
  • leetcode313-超级丑数

    原题 编写一段程序来查找第 n 个超级丑数。 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。 示例: 输入: n = 12, primes = [2…

    算法 2020年2月11日
    0110

发表回复

登录后才能评论