LeetCode 138. Copy List with Random Pointer【链表,DFS,迭代,哈希表】中等

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

本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库:https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你一个长度为 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 。

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

示例 1:
LeetCode 138. Copy List with Random Pointer【链表,DFS,迭代,哈希表】中等,链表,# BFS/DFS,# 哈希映射,leetcode,list,链表

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

示例 2:
LeetCode 138. Copy List with Random Pointer【链表,DFS,迭代,哈希表】中等,链表,# BFS/DFS,# 哈希映射,leetcode,list,链表

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

示例 3:
LeetCode 138. Copy List with Random Pointer【链表,DFS,迭代,哈希表】中等,链表,# BFS/DFS,# 哈希映射,leetcode,list,链表

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

提示:

  • 0 <= n <= 1000
  • -104 <= Node.val <= 10^4
  • Node.random 为 null 或指向链表中的节点。

类似题目:

  • 133. 克隆图

本题要求我们对一个特殊的链表进行深拷贝。如果是普通链表,我们可以直接按照遍历的顺序创建链表节点。而本题中因为随机指针的存在,当我们拷贝节点时,「当前节点的随机指针指向的节点」可能还没创建,因此我们需要变换思路

解法1 递归+哈希表

一个可行方案是,我们利用回溯的方式,让每个节点的拷贝操作相互独立。对于当前节点,我们首先要进行拷贝,然后我们进行「当前节点的后继节点」和「当前节点的随机指针指向的节点」拷贝,拷贝完成后将创建的新节点的指针返回,即可完成当前节点的两指针的赋值

具体地,我们用哈希表记录每一个节点对应新节点的创建情况。遍历该链表的过程中,我们检查「当前节点的后继节点」和「当前节点的随机指针指向的节点」的创建情况。如果这两个节点中的任何一个节点的新节点没有被创建,我们都立刻递归地进行创建。当我们拷贝完成,回溯到当前层时,我们即可完成当前节点的指针赋值。

注意一个节点可能被多个其他节点指向,因此我们可能递归地多次尝试拷贝某个节点,为了防止重复拷贝,我们需要首先检查当前节点是否被拷贝过,如果已经拷贝过,我们可以直接从哈希表中取出拷贝后的节点的指针并返回即可。

在实际代码中,我们需要特别判断给定节点为空节点的情况。

class Solution {
public:
    unordered_map<Node*, Node*> cachedNode;
    Node* copyRandomList(Node* head) {
        if (head == nullptr) return nullptr;
        if (!cachedNode.count(head)) {
            Node* headNew = new Node(head->val);
            cachedNode[head] = headNew;
            headNew->next = copyRandomList(head->next);
            headNew->random = copyRandomList(head->random);
        }
        return cachedNode[head];
    }
};

复杂度分析:

  • 时间复杂度: O ( n ) O(n) O(n) ,其中 n n n 是链表的长度。对于每个节点,我们至多访问其「后继节点」和「随机指针指向的节点」各一次,均摊每个点至多被访问两次。
  • 空间复杂度: O ( n ) O(n) O(n) ,其中 n n n 是链表的长度。为哈希表的空间开销。

解法2 迭代+哈希表

先用一个循环把新旧链表对应的两个结点捆绑在一个二元组里,然后再用一个循环完成对新链表每个结点的 n e x t next next 域和 r a n d o m random random 域的赋值:

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) return nullptr;
        unordered_map<Node*, Node*> cachedNode;
        
        Node* cur = head;
        while (cur) {
            cachedNode[cur] = new Node(cur->val);
            cur = cur->next;
        }
        cur = head;
        while (cur) {
            cachedNode[cur]->next = cachedNode[cur->next];
            cachedNode[cur]->random = cachedNode[cur->random];
            cur = cur->next;
        }
        return cachedNode[head];
    }
};

复杂度分析:

  • 时间复杂度: O ( n ) O(n) O(n) ,其中 n n n 是链表的长度。
  • 空间复杂度: O ( n ) O(n) O(n) ,其中 n n n 是链表的长度。为哈希表的空间开销。

解法3 迭代 + 节点拆分

注意到方法一、二需要使用哈希表记录每一个节点对应新节点的创建情况,而我们可以使用一个小技巧来省去哈希表的空间

  1. 首先将该链表中每一个节点拆分为两个相连的节点,例如对于链表 A → B → C A \rightarrow B \rightarrow C ABC ,我们可以将其拆分为 A → A ′ → B → B ′ → C → C ′ A \rightarrow A' \rightarrow B \rightarrow B' \rightarrow C \rightarrow C' AABBCC 。对于任意一个原节点 S S S ,其拷贝节点 S ′ S' S 即为其后继节点。
  2. 这样,我们可以直接找到「每一个拷贝节点 S ′ S' S 的随机指针」应当指向的节点,即为其「原节点 S S S 的随机指针指向的节点 T T T 」的后继节点 T ′ T' T 。需要注意原节点的随机指针可能为空,我们需要特别判断这种情况。
  3. 当完成了拷贝节点的随机指针的赋值,我们只需将这个链表按照原节点与拷贝节点的种类进行拆分即可,只需要遍历一次。同样需要注意最后一个拷贝节点的后继节点为空,我们需要特别判断这种情况。
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) return nullptr;
        for (Node* node = head; node; node = node->next->next) {
            Node* nodeNew = new Node(node->val);
            nodeNew->next = node->next;
            node->next = nodeNew;
        }
        for (Node* node = head; node; node = node->next->next) {
            Node* nodeNew = node->next;
            nodeNew->random = node->random ? node->random->next : nullptr;
        }
        Node* headNew = head->next;
        for (Node* node = head; node; node = node->next) {
            Node* nodeNew = node->next;
            node->next = node->next->next;
            nodeNew->next = nodeNew->next ? nodeNew->next->next : nullptr;
        }
        return headNew;
    }
};

复杂度分析:文章来源地址https://www.toymoban.com/news/detail-701000.html

  • 时间复杂度: O ( n ) O(n) O(n) ,其中 n n n 是链表的长度。如果在计算拷贝节点的随机指针的同时计算其后继指针,只需遍历两次(好像需要修改原链表)。
  • 空间复杂度: O ( 1 ) O(1) O(1) 。注意返回值不计入空间复杂度。

到了这里,关于LeetCode 138. Copy List with Random Pointer【链表,DFS,迭代,哈希表】中等的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构】[LeetCode138. 复制带随机指针的链表]

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

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

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

    2024年02月07日
    浏览(41)
  • 【刷题专栏—突破思维】LeetCode 138. 随机链表的复制

    前言 随机链表的复制涉及到复制一个链表,该链表不仅包含普通的next指针,还包含random指针,该指针指向链表中的任意节点或空节点。 题目链接: LeetCode 138. 随机链表的复制 题目介绍: 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指

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

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

    2024年02月04日
    浏览(46)
  • [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日
    浏览(52)
  • 单链表OJ题:LeetCode--138.复制带随即指针的链表

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

    2024年02月08日
    浏览(67)
  • LeetCode //C - 528. Random Pick with Weight

    You are given a 0-indexed array of positive integers w where w[i] describes the weight of the i t h i^{th} i t h index. You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w). For example, if w = [1, 3], the probability of

    2024年04月22日
    浏览(26)
  • leetcode链表题报错 runtime error: member access within null pointer of type ‘ListNode‘

    今天在做leetcode203:移除链表元素时,反复遇到了报错: runtime error: member access within null pointer of type ‘ListNode’ (solution.cpp) ,报错提示的意思是试图访问’ListNode空指针类型的成员,就浅浅记录一下修复bug的过程吧。。。。 刚开始的代码是这样的,逻辑是先建立一个头结点放

    2024年02月11日
    浏览(50)
  • LeetCode 865. Smallest Subtree with all the Deepest Nodes【树,DFS,BFS,哈希表】1534

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月09日
    浏览(43)
  • LeetCode 92. Reverse Linked List II【链表,头插法】中等

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月09日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包