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/

发表评论

电子邮件地址不会被公开。