【Leetcode】拿捏链表(五)——138. 复制带随机指针的链表

简介: 【Leetcode】拿捏链表(五)——138. 复制带随机指针的链表

作者:一个喜欢猫咪的的程序员

专栏:《Leetcode》

喜欢的话:世间因为少年的挺身而出,而更加瑰丽。                                  ——《人民日报》

目录

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


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


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

https://leetcode.cn/problems/copy-list-with-random-pointer/


题目描述:


示例:

示例 1:

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2:



输入:head = [[1,1],[2,1]]

输出:[[1,1],[2,1]]

示例 3:



输入:head = [[3,null],[3,0],[3,null]]

输出:[[3,null],[3,0],[3,null]]


思路:


题目的要求:

使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

本题我们分为三步完成:


  • 我们先将要复制的链表copy,先不管random我们先将val和next复制好。将cur和next来复制整个链表并将其链接在对应的数的后面。

fd100519cb3640d388e5b8f554e1e97d.gif

  • 链接完成后,我们开始处理random,我们链接后的链表是这样的。


当cur->random的下一个刚好是copy要链接的位置。因此当cur->random不为空时,copy->random=cur->random->next;cur->random为空时,置空就好了

当random处理完后,我们要将这两个链表拆开,并且保证两个链表要跟一开始一样、cur->next-next将链表变为原来的连接形式。我们用newhead来记录新链表的起始位置,copyTail来遍历链表将一个链表拆成两个链表。

时间复杂度:O(N)            空间复杂度:O(1)              

                     

代码实现:

struct Node* copyRandomList(struct Node* head) {
  struct Node*cur=head;
    while(cur)
    {
        struct Node*next=cur->next;
        struct Node*copy=(struct Node*)malloc(sizeof(struct Node));
        copy->val=cur->val;
        cur->next=copy;
        copy->next=next;
        cur=next;
    }
    cur=head;
    while(cur)
    {
        struct Node*copy=cur->next;
        if(cur->random)
        {
            copy->random=cur->random->next;
        }
        else
        {
            copy->random=NULL;
        }
        cur=copy->next;
    }
    cur=head;
    struct Node*copyTail=NULL;
    struct Node*newhead=NULL;
    while(cur)
    {
        struct Node*copy=cur->next;
        struct Node*next=copy->next;
        cur->next=next;
        if(copyTail==NULL)
        {
            newhead=copyTail=copy;
        }
        else
        {
            copyTail->next=copy;
            copyTail=copyTail->next;
        }
        cur=next;
    }
    return newhead;
}
相关文章
|
2月前
|
算法 容器
【算法】——双指针算法合集(力扣)
移动零,复写零,快乐数,盛最多水的容器,有效三角形的个数,和为s的两个数(查找总价格为目标值的两个商品 ),三数之和,四数之和
|
4月前
链表指针的传参,传值和传地址
本文讨论了链表操作中指针传参的问题,特别是指针的传值与传地址的区别,并提供了修正代码,以确保链表插入操作能正确地修改指针指向的地址。
32 1
链表指针的传参,传值和传地址
|
8月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
4月前
|
存储
一篇文章了解区分指针数组,数组指针,函数指针,链表。
一篇文章了解区分指针数组,数组指针,函数指针,链表。
35 0
|
4月前
|
C语言
无头链表二级指针方式实现(C语言描述)
本文介绍了如何在C语言中使用二级指针实现无头链表,并提供了创建节点、插入、删除、查找、销毁链表等操作的函数实现,以及一个示例程序来演示这些操作。
57 0
|
7月前
【数据结构OJ题】复制带随机指针的链表
力扣题目——复制带随机指针的链表
69 1
【数据结构OJ题】复制带随机指针的链表
|
6月前
|
Python
【Leetcode刷题Python】138. 复制带随机指针的链表
LeetCode上题目“138. 复制带随机指针的链表”的Python解决方案,包括两种方法:一种是在每个节点后复制一个新节点然后再分离出来形成新链表;另一种是构建一个字典来跟踪原始节点与其副本之间的映射关系,从而处理新链表的构建。
36 1
|
6月前
|
存储 算法 数据处理
指针与链表
指针与链表
108 0
|
8月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
8月前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表

热门文章

最新文章