《力扣刷题计划》复制带随机指针的链表

简介: 《力扣刷题计划》复制带随机指针的链表

06292fe942334609bf0405b73199cbc2.png🍑每一个结点有三个属性:

d991acc403164fc28f5a66d95cc950cd.png

🍑链表的样子大概是这样:

fed92f9e6eae9293eecae9300b2e44b0.png

注意这里我们复制的结点是引用类型,即我们复制的不只是结点的地址,我们需要复制的是旧结点。

比如一个这样的原链表


64da92dd8f4545d89bf103b1f15266df.png

我们的复制不是又生成一个和上面一模一样的链表出来,我们复制的是有着原来链表结构的新的链表

新的链表的每个结点所对应的值可能和原来链表的值相同,但next和random的肯定是不同的(但所对应的关系是相同的)


215b9987da3f4dbeb806ba64d8d60fc5.png

为了在新链表中持和原来链表中各个结点的对应关系,我们需要用Map来记录

比如上图中


b71f9496c0204e59b908fd6e13bcb63e.png

代码展示:

/*
// 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) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        Map<Node, Node> map = new HashMap<>(); // 如果用TreeMap里面放的元素一定是可比较的,只能用HashMap
        // 构建新旧结点的键值对关系,旧结点是Key,新结点是Value
        while (cur != null) {
            Node tmp = new Node(cur.val); // 构造新结点tmp,旧结点是cur
            map.put(cur, tmp);
            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); // 我们要返回的是新结点的head---及key(head) 所对应的 value值是map.get(head)
    }
}


相关文章
|
15小时前
|
存储 C语言
链表—初始化指针变和创建新的节点------区别应用分析
链表—初始化指针变和创建新的节点------区别应用分析
|
1天前
|
C语言 C++ 索引
力扣 138. 随机链表的复制
力扣 138. 随机链表的复制
|
7天前
LeetCode链表hard 有思路?但写不出来?
LeetCode链表hard 有思路?但写不出来?
|
7天前
教你三指针拿捏链表翻转
教你三指针拿捏链表翻转
|
7天前
|
索引
LeetCode438题(无敌双指针——滑动窗口)
LeetCode438题(无敌双指针——滑动窗口)
|
7天前
|
索引
每日一题:力扣328. 奇偶链表
每日一题:力扣328. 奇偶链表
15 4
|
7天前
leetcode代码记录(移除链表元素
leetcode代码记录(移除链表元素
12 0
【每日一题】LeetCode——反转链表
【每日一题】LeetCode——反转链表
【每日一题】LeetCode——链表的中间结点
【每日一题】LeetCode——链表的中间结点
|
18小时前
|
C语言