【LeetCode-中等题】138. 复制带随机指针的链表

这篇具有很好参考价值的文章主要介绍了【LeetCode-中等题】138. 复制带随机指针的链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

【LeetCode-中等题】138. 复制带随机指针的链表,力扣,# 中等题,leetcode,链表,算法

解题核心思路:找random指针指向

这里的拷贝属于深拷贝,就是不光是拷贝值,还要拷贝其指针的引用情况。如果只是单独的单向链表,则直接可以根据next指向找到下一个结点,然后创建一个新节点复制过来,直接拷贝,但是题目中的random指针指向的节点是没有归类的,这样我们就不可能使用普通的循环来进行拷贝,因为在拷贝的时候,你只能找到next,但是random并不知道,可能拷贝的同时random都还没创建出来

思路一:哈希

此题的复制,不单单要复制本身的.val值,还要把其next和random指向给复制过来。
那么我们可以借助一个哈希表Map来记录下旧链表的映射关系,key为旧链表的节点(包含next和random指向),value为新建的新节点(val值直接copy旧链表的节点)

【LeetCode-中等题】138. 复制带随机指针的链表,力扣,# 中等题,leetcode,链表,算法

  1. 建立哈希表,key为旧链表的节点,value为新建的新节点
  2. 然后去循环链表的同时,根据key取出新节点,并且(依据旧节点)设置新节点的next和random
  3. 最后返回新链表的首节点map.get(head);
    【LeetCode-中等题】138. 复制带随机指针的链表,力扣,# 中等题,leetcode,链表,算法

这里可以用纯哈希+while或者 哈希+递归的方法,原理都是一样的

思路二:迭代构造新链表

给每个旧链表节点后面都连上一个自己的复制节点,然后再根据老节点的random给后面的新节点附上,最后在把就新链表拆出来

  1. 构建新老链表结合体
    【LeetCode-中等题】138. 复制带随机指针的链表,力扣,# 中等题,leetcode,链表,算法

  2. 更新新节点的random
    【LeetCode-中等题】138. 复制带随机指针的链表,力扣,# 中等题,leetcode,链表,算法

  3. 拆链
    【LeetCode-中等题】138. 复制带随机指针的链表,力扣,# 中等题,leetcode,链表,算法文章来源地址https://www.toymoban.com/news/detail-684129.html

方法一:哈希+递归

 方法一 : 递归+哈希---->用哈希表记录旧值和新值的映射,让新值根据旧值的连接关系,构建新链表
    Map<Node, Node> map = new HashMap<Node, Node>();
    public Node copyRandomList(Node head) {
        if(head==null) return null;

        if(!map.containsKey(head)){//如果map集合不含head  则创建一份新的head进去  
         Node newHead = new Node(head.val);
         map.put(head,newHead);//key--->旧值  value--->新值   
         //给新值附上 next 和random
         newHead.next = copyRandomList(head.next);
         newHead.random = copyRandomList(head.random);
        }
        return map.get(head);
    }

方法二:纯哈希

方法二: 纯哈希----->  使用hash存储原结点和克隆结点的映射关系,通过映射关系处理克隆结点的random指针
    public Node copyRandomList(Node head) {
        if(head==null) return head;

        // map方法,空间复杂度O(n)
        Node oldNode = head;
       // 使用hash表存储旧结点和新结点的映射
        Map<Node,Node> map = new HashMap<>();
        while(oldNode != null){
            Node newNode = new Node(oldNode.val);
            map.put(oldNode,newNode);
            oldNode = oldNode.next;
        }

        oldNode = head;//重置 oldNode 位置到head头结点
        while(oldNode != null){ //根据旧node 映射新node
        map.get(oldNode).next = map.get(oldNode.next);
        map.get(oldNode).random = map.get(oldNode.random);
        oldNode = oldNode.next;
        }
        return map.get(head);//返回头结点的映射新节点
    }

方法三:迭代 + 节点拆分

/ 方法三: 迭代 + 节点拆分---->  给每一个旧的链表节点去拼接一个新的到旧节点后面,然后将新结点的random指向旧节点的random指向,最后再把新的节点拆分出来
public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        // for (Node node = head; node != null; node = node.next.next) {
        //     Node nodeNew = new Node(node.val);
        //     nodeNew.next = node.next;
        //     node.next = nodeNew;
        // }
        // 第一次遍历,拼接新旧链表 旧1-->新1-->旧2--->新2
        Node node = head;
        while(node != null){
             Node nodeNew = new Node(node.val);
             nodeNew.next = node.next;
             node.next = nodeNew;
             node = node.next.next;
        }
        // for (Node node = head; node != null; node = node.next.next) {
        //     Node nodeNew = node.next;
        //     if(node.random != null) nodeNew.random = node.random.next;
        //     else nodeNew.random = null;
        // }
        // 第二次遍历,给新结点连上旧节点的random
         node = head;// 重置node到head位置
        while(node != null){
            Node nodeNew = node.next;
            if(node.random != null) nodeNew.random = node.random.next; 
            //如果旧节点的random指向null  null本身没有新节点,则直接让新节点的random指向null
            else nodeNew.random = null;
            node = node.next.next;
        }

        Node headNew = head.next;
        // for (Node node = head; node != null; node = node.next) {
        //     Node nodeNew = node.next;
        //     node.next = node.next.next;
        //     if(nodeNew.next != null) nodeNew.next = nodeNew.next.next;
        //     else nodeNew.next = null;
        // }
        node = head;// 重置node到head位置
        // 第三次遍历,拆分新链表出来
        while(node != null){
            Node nodeNew = node.next;
            node.next = nodeNew.next;
            if(nodeNew.next != null) nodeNew.next = nodeNew.next.next;
            else nodeNew.next = null;//防止最后一个新链表nodeNew.next.next出现空指针
            node = node.next;
        }
        return headNew;
    }

到了这里,关于【LeetCode-中等题】138. 复制带随机指针的链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 138. 复制带随机指针的链表(深拷贝)题解

    给你一个长度为  n  的链表,每个节点包含一个额外增加的随机指针  random  ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的  深拷贝 。 深拷贝应该正好由  n  个  全新  节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的  next  指针和

    2024年02月13日
    浏览(44)
  • 力扣-复制带随机指针的链表

    给你一个长度为  n  的链表,每个节点包含一个额外增加的随机指针  random  ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的  深拷贝 。 深拷贝应该正好由  n  个  全新  节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的  next  指针和

    2024年02月11日
    浏览(47)
  • 单链表OJ题:LeetCode--138.复制带随即指针的链表

    朋友们、伙计们,我们又见面了,本期来给大家解读一下LeetCode中第138道单链表OJ题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! 数据结构与算法专栏 : 数据结构与算法 个  人  主  页  : stackY、 C 语 言 专 栏 : C语言:从入门到精通  Lee

    2024年02月08日
    浏览(68)
  • 【LeetCode】 复制带随机指针的链表

    Leetcode 138.复制带随机指针的链表 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节

    2024年02月08日
    浏览(48)
  • 力扣每日一道系列 --- LeetCode 138. 随机链表的复制

    📷 江池俊: 个人主页 🔥个人专栏: ✅数据结构探索 ✅LeetCode每日一道 🌅 有航道的人,再渺小也不会迷途。 LeetCode 138. 随机链表的复制 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的

    2024年02月04日
    浏览(47)
  • Leetcode刷题之复制带随机指针的链表

    生命不是安排,而是追求,人生的意义也许永远没有答案,但也要尽情感受这种没有答案的人生。                                                                                                                     --弗吉尼亚.  伍尔芙         目录 前言:

    2024年02月04日
    浏览(45)
  • 【LeetCode】数据结构题解(9)[复制带随机指针的链表]

    所属专栏:玩转数据结构题型❤️ 🚀 博主首页:初阳785❤️ 🚀 代码托管:chuyang785❤️ 🚀 感谢大家的支持,您的点赞和关注是对我最大的支持!!!❤️ 🚀 博主也会更加的努力,创作出更优质的博文!!❤️ 🚀 关注我,关注我,关注我,重要的事情说三遍!!!!!

    2024年02月11日
    浏览(59)
  • 【数据结构】LeetCode升级版的环形链表,复制带随机指针的链表

              1、题目说明           2、题目解析           1、题目说明           2、题目解析      1、题目说明 题目链接: 升级版的环形链表  给定一个链表的头节点 head ,返回链表开始入环的第一个节点。  如果链表无环,则返回NULL。 如果链表中有某个节点,可以通

    2024年01月16日
    浏览(62)
  • 【链表OJ 11】复制带随机指针的链表

    前言:  💥🎈个人主页:​​​​​​Dream_Chaser~ 🎈💥 ✨✨刷题专栏:http://t.csdn.cn/UlvTc ⛳⛳本篇内容:力扣上链表OJ题目 目录 leetcode138. 复制带随机指针的链表 1. 问题描述 2.代码思路: 2.1拷贝节点插入到原节点的后面 2.2控制拷贝节点的random     2.3拷贝节点解下来尾插组成拷

    2024年02月09日
    浏览(51)
  • 【数据结构】两两交换链表 && 复制带随机指针的链表

    给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。 使用一个栈S来存储相邻两个节点即可 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以

    2024年04月15日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包