单链表OJ题:LeetCode--138.复制带随即指针的链表

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

朋友们、伙计们,我们又见面了,本期来给大家解读一下LeetCode中第138道单链表OJ题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成!

数据结构与算法专栏数据结构与算法

个  人  主  页 :stackY、

C 语 言 专 栏C语言:从入门到精通

单链表OJ题:LeetCode--138.复制带随即指针的链表

 LeetCode--138.复制带随即指针的链表:https://leetcode.cn/problems/copy-list-with-random-pointer/description/

目录

1.题目介绍

2.实例演示

3.解题思路

::链接拷贝结点 :: 

::找拷贝节点的random ::

:: 拆解拷贝链表 ::


1.题目介绍

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

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

单链表OJ题:LeetCode--138.复制带随即指针的链表

小编现在这里向大家袒露心扉一下:其实我刚刚看到这个单链表OJ题,看了半天连题目都没咋搞明白,好不容易看懂了题目介绍,可是又不知道该从何下手,然后求助各种大佬,才慢慢理解,然后整理思路,在这篇文章中将这道题分享给大家。

2.实例演示

单链表OJ题:LeetCode--138.复制带随即指针的链表

3.解题思路

这道题应该算是单链表OJ题中比较复杂的一道题了,主要是比较难理解。题目的主要意思就是要拷贝出与原链表一模一样的一个链表。那么这道题拷贝链表都不是很复杂,比较难处理的就是这个随即指针random的指向,如果原链表的random指向空那这好说,拷贝链表的也指向空,但是如果原链表的random指向非空,那该如何去找这个random呢?在这里呢,很多老铁喜欢用random指向的值来比较,这种想法可以,但是架不住链表中有相同的值,那么就有许多老铁用它的random指向的地址来比较,这种方法是完全可行的,但是呢,这种暴力求解的方法往往都不是最优解,使用地址来进行比较的话它的时间复杂度是O(N^2),效率也是不太行。所以我们需要寻求更优解

这道题的解题思路我分为了三个步骤:

1. 链接拷贝结点:

 将拷贝结点插入到原结点的后面。

2. 找拷贝节点的random:

通过原链表来控制拷贝结点的随机指针random。

3. 拆解拷贝链表:

将拷贝结点拆下来,依次尾插组成新的链表,然后恢复原链表。

接下来我们一步一步来进行解题:

::链接拷贝结点 :: 

我们可以将拷贝结点链接在原结点的后面,这种方法比较巧妙,有助于我们找随即指针random。

先创建拷贝节点,然后遍历原链表,然后保存头节点的下一个结点,改变指向,将拷贝节点插入到原结点的后面。

图示:

单链表OJ题:LeetCode--138.复制带随即指针的链表

 

代码演示:

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

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur = head;

    //1.链接拷贝节点
    while(cur)
    {
        //创建拷贝结点
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;

        //保存头指针的下一个结点
        struct Node* curNext = cur->next;

        //链接
        cur->next = copy;
        copy->next = curNext;
        cur = curNext;
    }
    //......
}

 ::找拷贝节点的random ::

当我们将拷贝结点链接在原结点的后面时,我们需要找拷贝结点的随机指针random,这里可以分为两种情况:

1. 如果原结点的random是空,那么直接将拷贝结点的random置为空即可。

2. 若不为空,那么就需要观察一下这个链表,拷贝结点的random指针指向的就是原结点的random指向的结点的next结点:

                               copy -> random = cur -> random -> next;

因为我们将拷贝结点链接在了原结点的后面,那么原结点的random指向的结点的next结点就是拷贝结点要找的random。我们依旧遍历整个链表,然后将拷贝节点的随机指针链接。

图示:

单链表OJ题:LeetCode--138.复制带随即指针的链表

 

代码演示:

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

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur = head;

    //1.链接拷贝节点
    while(cur)
    {
        //创建拷贝结点
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;

        //保存头指针的下一个结点
        struct Node* curNext = cur->next;

        //链接
        cur->next = copy;
        copy->next = curNext;
        cur = curNext;
    }

    //2.找拷贝节点的random 
    //重新返回头
    cur = head;
    while(cur)
    {
        //找拷贝结点
        struct Node* copy = cur->next;
        //找下一个结点
        struct Node* next = copy->next;

        //链接拷贝节点的随机指针random
        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }

        //遍历
        cur = next;
    }
    //......
}

:: 拆解拷贝链表 ::

我们找到了拷贝链表之后呢,需要将这些拷贝的结点组成一个新的链表,这就需要将这些拷贝结点依次进行尾插,然后再将原链表恢复。这就比较简单了:

图示:

单链表OJ题:LeetCode--138.复制带随即指针的链表

 完整代码演示:

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

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur = head;

    //1.链接拷贝节点
    while(cur)
    {
        //创建拷贝结点
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;

        //保存头指针的下一个结点
        struct Node* curNext = cur->next;

        //链接
        cur->next = copy;
        copy->next = curNext;
        cur = curNext;
    }

    //2.找拷贝节点的random 
    //重新返回头
    cur = head;
    while(cur)
    {
        //找拷贝结点
        struct Node* copy = cur->next;
        //找下一个结点
        struct Node* next = copy->next;

        //链接拷贝节点的随机指针random
        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }

        //遍历
        cur = next;
    }

    //3.拆解拷贝结点,恢复原链表
    //重新返回头
    cur = head;

    //创建新的链表
    struct Node* copyHead = NULL;
    struct Node* copyTail = NULL;

    while(cur)
    {
        //找拷贝结点
        struct Node* copy = cur->next;
        //找下一个结点
        struct Node* next = copy->next;

        //尾插拷贝节点构成新的链表
        if(copyTail == NULL)
        {
            copyHead = copyTail = copy;
        }
        else
        {
            copyTail->next = copy;
            copyTail = copyTail->next;
        }

        //恢复原链表
        cur->next = next;
        cur = next;
    }
    
    return copyHead;

}

朋友们、伙计们,美好的时光总是短暂的,我们本期的的分享就到此结束,最后看完别忘了留下你们弥足珍贵的三连喔,感谢大家的支持!文章来源地址https://www.toymoban.com/news/detail-479312.html

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

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

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

相关文章

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

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

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

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

    2024年02月13日
    浏览(40)
  • 【链表OJ 11】复制带随机指针的链表

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

    2024年02月09日
    浏览(47)
  • 【数据结构OJ题】复制带随机指针的链表

    原题链接:https://leetcode.cn/problems/copy-list-with-random-pointer/description/ 目录 1. 题目描述 2. 思路分析 3. 代码实现 此题可以分三步进行: 1. 拷贝链表的每一个结点,拷贝的结点先链接到被拷贝结点的后面。 2. 复制随机指针的链接:拷贝结点的随机指针指向被拷贝结点随机指针的下

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

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

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

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

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

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

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

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

    2024年01月16日
    浏览(57)
  • 力扣-复制带随机指针的链表

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

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

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

    2024年04月15日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包