力扣每日一道系列 --- LeetCode 138. 随机链表的复制

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


力扣每日一道系列 --- LeetCode 138. 随机链表的复制,LeetCode每日一道,leetcode,链表,linux

📷 江池俊: 个人主页
🔥个人专栏: ✅数据结构探索 ✅LeetCode每日一道
🌅 有航道的人,再渺小也不会迷途。

LeetCode 138. 随机链表的复制

力扣每日一道系列 --- LeetCode 138. 随机链表的复制,LeetCode每日一道,leetcode,链表,linux

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

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

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

返回复制链表的头节点。

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

  • val:一个表示 Node.val 的整数。
  • random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null

你的代码 接受原链表的头节点 head 作为传入参数。

力扣每日一道系列 --- LeetCode 138. 随机链表的复制,LeetCode每日一道,leetcode,链表,linux

迭代 + 节点拆分

思路及算法:

此处的难点就是如何 copy 深拷贝的节点的 random ?
思路是:将 copy 的节点依次插入到相应节点的后面,从而保证 copy 与相应的节点保持联系,而要找 copy 的节点的 random
就是先找到与 copy 对应的节点的 random ,而 randomnext 就是 copy 节点的 random ,因为 copy 节点是对应节点的后一个节点,故 copy 节点的 random 就是对应节点的后一个,它们对应的位置是不变的,copy 节点总是对应节点的后一个位置这里可以理解为假设你目前是一个单身狗,你想要找一个女朋友,而你的好兄弟有女朋友这时,你通过你跟你好兄弟的这层关系就可以去找好兄弟的女朋友把他的闺蜜介绍给你。文章来源地址https://www.toymoban.com/news/detail-756457.html

  1. 我们首先将该链表中每一个节点拆分为两个相连的节点,例如对于链表 A→B→C,我们可以将其拆分为 A→A′→B→B′→C→C′
    对于任意一个原节点 S,其拷贝节点 S′ 即为其后继节点。
  2. 这样,我们可以直接找到每一个拷贝节点 S′ 的随机指针应当指向的节点,即为其原节点 S 的随机指针指向的节点 T 的后继节点
    T′。需要注意原节点的随机指针可能为空,我们需要特别判断这种情况。
  3. 当我们完成了拷贝节点的随机指针的赋值,我们只需要将这个链表按照原节点与拷贝节点的种类进行拆分即可,只需要遍历一次。同样需要注意最后一个拷贝节点的后继节点为空,我们需要特别判断这种情况。
    力扣每日一道系列 --- LeetCode 138. 随机链表的复制,LeetCode每日一道,leetcode,链表,linux力扣每日一道系列 --- LeetCode 138. 随机链表的复制,LeetCode每日一道,leetcode,链表,linux
    力扣每日一道系列 --- LeetCode 138. 随机链表的复制,LeetCode每日一道,leetcode,链表,linux力扣每日一道系列 --- LeetCode 138. 随机链表的复制,LeetCode每日一道,leetcode,链表,linux
struct Node* copyRandomList(struct Node* head) {
    if(head==NULL)
    {
        return NULL;
    }
    //1.复制对应的链表节点,并连接在相应链表节点的后面
    struct Node* cur = head;
    while(cur)
    {
        struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
        newnode->val = cur->val;
        newnode->next = cur->next;
        cur->next = newnode;
        cur = newnode->next;
    }
    //2.处理复制链表节点的random
    cur = head;
    while(cur)
    {
        if(cur->random)
            cur->next->random = cur->random->next;
        else
            cur->next->random = NULL;
        cur = cur->next->next;
    }
    //3.将原链表和复制链表拆分开,返回复制链表的头节点
    struct Node* newhead = head->next;
    struct Node* newcur = newhead;
    head->next = head->next->next;
    cur = head->next;
    while(cur)
    {
        newcur->next = newcur->next->next;
        newcur = newcur->next;
        cur->next = cur->next->next;
        cur = cur->next;
    }
    newcur->next = NULL;
    return newhead;
}

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

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

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

相关文章

  • [LeetCode]-160. 相交链表-141. 环形链表-142.环形链表II-138.随机链表的复制

    目录 160.相交链表  题目 思路 代码  141.环形链表  题目 思路 代码 142.环形链表II 题目 思路 代码 160. 相交链表 - 力扣(LeetCode) https://leetcode.cn/problems/intersection-of-two-linked-lists/description/ 给你两个单链表的头节点  headA  和  headB  ,请你找出并返回两个单链表相交的起始节点

    2024年02月05日
    浏览(48)
  • 力扣每日一道系列 --- LeetCode 88. 合并两个有序数组

    📷 江池俊: 个人主页 🔥个人专栏: ✅数据结构探索 ✅LeetCode每日一道 🌅 有航道的人,再渺小也不会迷途。 LeetCode 88. 合并两个有序数组 首先创建一个临时数组,其大小为第一个数组的大小(即nums1Size),其作用主要是。 通过循环遍历两个数组,将两个数组元素比较后较

    2024年02月04日
    浏览(48)
  • LeetCode 138.复制带随机指针的链表

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

    2024年02月11日
    浏览(44)
  • 【LeetCode-中等题】138. 复制带随机指针的链表

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

    2024年02月10日
    浏览(44)
  • 【数据结构】[LeetCode138. 复制带随机指针的链表]

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

    2024年02月04日
    浏览(46)
  • leetcode做题笔记138. 复制带随机指针的链表

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

    2024年02月07日
    浏览(39)
  • (链表) 剑指 Offer 52. 两个链表的第一个公共节点 ——【Leetcode每日一题】

    难度:简单 输入两个链表,找出它们的第一个公共节点。 如下面的两个链表: 在节点 c1 开始相交。 示例 1: 输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出:Reference of the node with value = 8 输入解释:相交节点的值为 8 (注意,如果两个列表相交则

    2024年02月15日
    浏览(51)
  • Leetcode-每日一题【剑指 Offer 35. 复杂链表的复制】

    请实现  copyRandomList  函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个  next  指针指向下一个节点,还有一个  random  指针指向链表中的任意节点或者  null 。 示例 1: 输入: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出: [[7,null],[13,0],[11,4],[10,2],[1,0]] 示例 2: 输入

    2024年02月11日
    浏览(41)
  • 138. 复制带随机指针的链表

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

    2024年02月13日
    浏览(62)
  • 138. 复制带随机指针的链表(深拷贝)题解

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

    2024年02月13日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包