草庐IT

LeetCode-复制带随机指针的链表

养乌龟的小少年 2023-08-30 原文

题目描述：

给你一个长度为 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 作为传入参数。

图示：

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

目录

1.解题思路 

1.1思路1：

1.2思路2 ：

2.软件编程 

2.1拷贝节点，链接进原节点

2.2处理random节点 

 2.3深度拷贝

 

1.解题思路 

1.1思路1：

第一步：首先通过便利的方法，将每个节点拷贝一份，且next指针明确。如下图示：

第二步：处理random指针， 首先需要明确的是我们是对原链表进行的拷贝，新链表和原链表已经没有联系，我们不可以通过原链表的指针去寻找random指向，更不可能通过数值去寻找random指向，如果有相同值得节点，random该指向谁呢？如下图所示：

 所以，靠数值寻找random指向是不合理的，会出现重复值得情况，导致指向出问题。

第三步：我们通过相对位置，去寻找random指向，譬如头结点是位置0，依次是1、2、3、等，当我们寻找13指向就是相对头结点偏移零个位置，11的random指向就是相对头结点 偏移4个位置。

这个方法虽然能实现深层拷贝，但是时间复杂度是O()。

1.2思路2 ：

 第一步：在原链表的基础上，新增跟原链表相同的节点，并插入到对应数值得节点之后，

如下图所示：

 

第二步：处理random节点，当我们复制新的节点在对应节点之后，新节点的random 就是原节点random 的拷贝也就是next，图示如下：

第三步: 深度拷贝

我们需要将拷贝好的节点，取下来重新next指向完成深度拷贝，然后恢复原节点指向，图解如下：

2.软件编程 

2.1拷贝节点，链接进原节点

struct Node* copyRandomList(struct Node* head) {
    //插入拷贝的节点，链接进原链表
    struct Node* cur = head;//定义遍历节点
    while(cur)
    {
        struct Node* copy = (struct Node *)malloc(sizeof(struct Node));//复制节点堆上申请
        struct Node* next = cur->next;//记录下一个节点指向
        if(copy == NULL)
        {
            perror("malloc:fail");
            exit(-1);

        }
        copy->val = cur->val;
      
        cur->next = copy;
        copy->next = next;
        cur = next;
    }

2.2处理random节点 

    //处理随机节点指向
    cur = head;
    while(cur)
    {
      struct Node* copy = cur->next;
      if(cur->random == NULL)
      {
          copy->random = NULL;
      }
      else
      {
          copy->random = cur->random->next;
      }
      cur = copy->next;
    }

 2.3深度拷贝

 

    //深度拷贝

     struct Node*copyhead = NULL,*copytail = NULL;
      cur = head;
     
      while(cur)
      {
           struct Node *copy = cur->next;
           struct Node *next = copy->next;
          if(copyhead == NULL)
          {
              copyhead = copytail = cur->next;
          }
          else
          {
               copytail->next = copy;
             copytail = copytail->next;
          }
         
          cur->next = next;
          cur = next;
      }

return copyhead;

LeetCode复制带xffxff0cxff0链表数据结构

有关LeetCode-复制带随机指针的链表的更多相关文章

  1. 华为OD机试用Python实现 -【明明的随机数】 2023Q1A - 2

    华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o

  2. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  3. ruby - 如何在 ruby​​ 中复制目录结构，不包括某些文件扩展名 - 2

    我想编写一个ruby​​脚本来递归复制目录结构，但排除某些文件类型。因此，给定以下目录结构:folder1folder2file1.txtfile2.txtfile3.csfile4.htmlfolder2folder3file4.dll我想复制这个结构，但不包含.txt和.cs文件。因此，生成的目录结构应如下所示:folder1folder2file4.htmlfolder2folder3file4.dll 最佳答案 您可以使用查找模块。这是一个代码片段:require"find"ignored_extensions=[".cs"

  4. ruby - 如何在 Ruby 中生成一个非常大的随机整数？ - 2

    我想在ruby​​中生成一个64位整数。我知道在Java中你有很多渴望，但我不确定你会如何在Ruby中做到这一点。另外，64位数字中有多少个字符？这是我正在谈论的示例......123456789999。@num=Random.rand(9000)+Random.rand(9000)+Random.rand(9000)但我认为这是非常低效的，必须有一种更简单、更简洁的方法来做到这一点。谢谢! 最佳答案 rand可以将范围作为参数:pa=rand(2**32..2**64-1)#=>11093913376345012184putsa.

  5. ruby 变量作为同一对象(指针？) - 2

    >>a=5=>5>>b=a=>5>>b=4=>4>>a=>5如何将“b”设置为实际的“a”，以便在示例中，变量a也将变为4。谢谢。 最佳答案 classRefdefinitializeval@val=valendattr_accessor:valdefto_s@val.to_sendenda=Ref.new(4)b=aputsa#=>4putsb#=>4a.val=5putsa#=>5putsb#=>5当您执行b=a时，b指向与a相同的对象(它们具有相同的object_id).当你执行a=some_other_thing时，a将指向

  6. ruby - 在两个 ActiveRecord 类之间合并/复制属性的好方法？ - 2

    之前有人问过这个问题，我发现了以下clip关于如何一次设置一个类对象的所有属性，但由于批量分配保护，这在Rails中是不可能的。(例如，您不能Object.attributes={})有没有一种很好的方法可以将一个类的属性合并到另一个类中？object1.attributes=object2.attributes.inject({}){|h,(k,v)|h[k]=vifObjectModel.column_names.include?(k);h}谢谢。 最佳答案 利用assign_attributes使用:without_prote

  7. ruby-on-rails - 多次选择一个随机数，但绝不会两次选择相同的随机数 - 2

    这个问题在这里已经有了答案:关闭10年前。PossibleDuplicate:HowdoIgeneratealistofnuniquerandomnumbersinRuby?我想做的事:Random.rand(0..10).timesdoputsRandom.rand(0..10)end但如果随机数已经显示过，则无法再次显示。如何最轻松地做到这一点？

  8. ruby - 以随机顺序将数组拆分为多个数组 - Ruby - 2

    我试图在每次运行时以随机顺序将一个名称数组拆分为多个数组。我知道如何拆分它们:name_array=["bob","john","rob","nate","nelly","michael"]array=name_array.each_slice(2).to_a=>[["bob","john"],["rob","nate"],["nelly","michael"]]但是，如果我希望它每次都以随机顺序吐出它们怎么办？ 最佳答案 在做同样的事情之前，打乱数组。(Array#shuffle)name_array.shuffle.each_s

  9. Ruby:我怎样才能复制这个数组？ - 2

    (跟进我之前的问题，Ruby:howcanIcopyavariablewithoutpointingtothesameobject?)我正在编写一个简单的Ruby程序来在.svg文件中进行一些替换。第一步是从文件中提取信息并将其放入数组中。为了避免每次调用此函数时都从磁盘读取文件，我尝试使用memoize设计模式-在第一次调用后的每次调用中都使用缓存结果。为此，我使用了一个在函数之前定义的全局变量。但是，即使我在返回局部变量之前将该变量.dup为局部变量，调用该变量的函数仍在修改全局变量。这是我的实际代码:#memoizetokeepfromhavingtoreadoriginalfi

  10. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

随机推荐