【刷题专栏—突破思维】LeetCode 138. 随机链表的复制

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

【刷题专栏—突破思维】LeetCode 138. 随机链表的复制,【刷题专栏—突破思维】,leetcode,链表,C语言,算法

前言
随机链表的复制涉及到复制一个链表,该链表不仅包含普通的next指针,还包含random指针,该指针指向链表中的任意节点或空节点。



题目链接: LeetCode 138. 随机链表的复制

原地修改链表

题目介绍:
给你一个长度为 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 。

示例1:
【刷题专栏—突破思维】LeetCode 138. 随机链表的复制,【刷题专栏—突破思维】,leetcode,链表,C语言,算法
输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例2:
【刷题专栏—突破思维】LeetCode 138. 随机链表的复制,【刷题专栏—突破思维】,leetcode,链表,C语言,算法
输入:head = [[3,null],[3,0],[3,null]]
输出:[[3,null],[3,0],[3,null]]


【刷题专栏—突破思维】LeetCode 138. 随机链表的复制,【刷题专栏—突破思维】,leetcode,链表,C语言,算法

  1. 第一次遍历:复制节点并插入到原节点后面
    • 对于每个原节点,创建一个新节点,并将新节点插入到原节点后面。
    • 新节点的val和next指针与原节点相同,而random指针初始化为NULL。

【刷题专栏—突破思维】LeetCode 138. 随机链表的复制,【刷题专栏—突破思维】,leetcode,链表,C语言,算法

struct Node* current = head;
while (current != NULL) {
    struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
    copy->val = current->val;
    copy->next = current->next;
    copy->random = NULL;
    current->next = copy;
    current = copy->next;
}
  1. 第二次遍历:更新复制节点的 random 指针

    • 对于每个原节点,如果其random指针不为NULL,则将对应的复制节点的random指针指向原节点的random指针的下一个节点。

【刷题专栏—突破思维】LeetCode 138. 随机链表的复制,【刷题专栏—突破思维】,leetcode,链表,C语言,算法

current = head;
while (current != NULL) {
    if (current->random != NULL) {
        current->next->random = current->random->next;
    }
    current = current->next->next;
}
  1. 第三次遍历:拆分原链表和复制链表

    • 将链表拆分为原链表和复制链表,同时恢复原链表的next指针。

【刷题专栏—突破思维】LeetCode 138. 随机链表的复制,【刷题专栏—突破思维】,leetcode,链表,C语言,算法

struct Node* newHead = head->next;
struct Node* newCurrent = newHead;
current = head;
while (current != NULL) {
    current->next = newCurrent->next;
    current = current->next;
    if (current != NULL) {
        newCurrent->next = current->next;
        newCurrent = newCurrent->next;
    }
}

【刷题专栏—突破思维】LeetCode 138. 随机链表的复制,【刷题专栏—突破思维】,leetcode,链表,C语言,算法
如果你喜欢这篇文章,点赞👍+评论+关注⭐️哦!
欢迎大家提出疑问,以及不同的见解。文章来源地址https://www.toymoban.com/news/detail-753657.html

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

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

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

相关文章

  • LeetCode 138.复制带随机指针的链表

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

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

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

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

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

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

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

    2024年02月07日
    浏览(38)
  • 【Leetcode刷题】链表的中间结点和合并两个有序链表

    生命如同寓言,其价值不在与长短,而在与内容。                                ——塞涅卡 目录 一.链表的中间结点 1.快慢指针 二.合并两个有序链表  1.尾插法 给你单链表的头结点 head ,请你找出并返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点

    2023年04月17日
    浏览(42)
  • 反转链表、链表的中间结点、合并两个有序链表【LeetCode刷题日志】

    给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 这里解释一下三个指针的作用: n1:记录上一个节点,如果是第一个就指向空 n2:记录此节点的位置 n3:记录下一个节点的位置,让翻转后能找到下一个节点

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

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

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

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

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

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

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

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

    2024年02月08日
    浏览(62)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包