复制带随机指针的链表

如果你不相信努力和时光,那么成果就会是第一个选择辜负你的。不要去否定你自己的过去,也不要用你的过去牵扯你现在的努力和对未来的展望。不是因为拥有希望你才去努力,而是去努力了,你才有可能看到希望的光芒。复制带随机指针的链表,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

💕“如果你关注自己已经拥有的,你就会拥有更多。如果你只关注自己没有得到的,你永远不会满足。” – 奥普拉·温弗瑞💕
🐼作者:不能再留遗憾了🐼
🎆专栏:Java学习🎆
🚗本文章主要内容:leetcode之复制带随机指针的链表题解
在这里插入图片描述

leetcode之复制带随机指针的链表(难度:中等)

题目要求

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

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如,如果原链表中有 X 和 Y 两个节点,其中 X.random –> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random –> y 。

返回复制链表的头节点。

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

val:一个表示 Node.val 的整数。
random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

示例:
在这里插入图片描述

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        
    }
}

做题思路

注意题目理解:深拷贝,意思是重新开辟一个内存,这个新地址所在的内存包含原来地址的所有内容,并且这个新地址里面的内容也是新开辟的,跟之前的内容并没有关系,只是数值上是相同的。

在这里插入图片描述

知道了题目的意思了,那么接下来我们要做的就是怎样做出这道题。根据题目意思:新复制的链表的val相同,next和random的指向相对相同,所以我们可以借助HashMap,将cur作为key,新复制的节点newNode作为value,这样我们就可以根据这个key-value结构来找到新复制的节点的next和random指向相对于原链表位置的节点的value节点。

在这里插入图片描述

我们第一遍遍历原链表的时候,每遍历一个节点我们就把这个节点放在对应key处,然后新开辟一个相等val的节点放在该key的value处。
第二遍遍历的时候我们就将新复制的链表的next和random指向对应的位置。

在这里插入图片描述

代码实现

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        while(cur != null) {
            Node newNode = new Node(cur.val);
            map.put(cur,newNode);
            cur = cur.next;
        }
        cur = head;
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }

        return map.get(head);
    }
}

在这里插入图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之家整理,本文链接:https://www.bmabk.com/index.php/post/192637.html

(0)
飞熊的头像飞熊bm

相关推荐

发表回复

登录后才能评论
极客之家——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!