剑指Offer(二十五):复杂链表的复制

2017年12月13日11:16:03 8 7,293 °C
摘要

输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)

剑指Offer(二十五):复杂链表的复制

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)

1、思路

大部分人首先想到的可能是先复制复杂指针的label和next,然后再查找random并更新。查找random又分为两种,一种是每次都从头查找,时间复杂度为O(n^2);另一种是空间换时间,复制label和next的同时建立一个hash表来存放新旧复杂指针的对应关系,所以后续只需一步就能找到random,算法时间复杂度为O(n)。

我们这里将复杂链表的复制过程分解为三个步骤。在写代码的时候我们每一步定义一个函数,这样每个函数完成一个功能,整个过程的逻辑也就非常清晰明了了。

我们这里采用三步:

  • 第一步:复制复杂指针的label和next。但是这次我们把复制的结点跟在元结点后面,而不是直接创建新的链表;
  • 第二步:设置复制出来的结点的random。因为新旧结点是前后对应关系,所以也是一步就能找到random;
  • 第三步:拆分链表。奇数是原链表,偶数是复制的链表。

有图思路更清晰:

剑指Offer(二十五):复杂链表的复制

剑指Offer(二十五):复杂链表的复制

剑指Offer(二十五):复杂链表的复制

2、代码

C++:

weinxin
微信公众号
分享技术,乐享生活:微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:8   其中:访客  6   博主  2

    • avatar KodChen 来自天朝的朋友 谷歌浏览器 Windows 10 辽宁省沈阳市 东北大学 1

      递归方法是不是更简洁一些~

        • avatar Jack Cui Admin 这家伙可能用了美佬的代理 谷歌浏览器 Windows 10 美国 弗吉尼亚州

          @KodChen 嗯,是的。可以用递归方法写一个。

        • avatar cgzjdx 来自天朝的朋友 Safari浏览器 Mac OS X 10_13_6 广东省肇庆市 鹏博士长城宽带 2

          您好,我有个问题,对于第三个函数RandomListNode* ReconnectNodes,其中的这一部分
          if(pNode != NULL){
          pClonedHead = pClonedNode = pNode->next;
          pNode->next = pClonedNode->next;
          pNode = pNode->next;
          }
          我把他改为
          if(pNode != NULL){
          pClonedHead = pClonedNode = pNode->next;
          pNode = pNode->next->next;
          }
          为什么在牛客网上就不能通过了呢。。我觉得这两种写法应该是一样的。

            • avatar cgzjdx 来自天朝的朋友 Safari浏览器 Mac OS X 10_13_6 广东省肇庆市 鹏博士长城宽带 2

              @cgzjdx 我在自己电脑上写了一遍,两种写法都试了,得到的结果是一样的,不知道为什么牛客网上运行不能通过。

                • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点

                  @cgzjdx pNode->next不管了?

              • avatar 小白 来自天朝的朋友 谷歌浏览器 Windows 10 广东省广州市 联通 1

                python3.* 的解法,你看可行?
                a = [1,2,3,4,5]

                import copy
                result = copy.deepcopy(a)

                • avatar alex 来自天朝的朋友 谷歌浏览器 Windows 10 江苏省苏州市昆山市 电信 0

                  请教下这两句:pNode->next = pCloned;pNode = pCloned->next;我的理解这个应该就是插入新节点这样一个过程,第一句看起来是把new的节点跟在原始链表head后边,第二句话没明白,感觉应该是把new的节点指向原节点的第二个节点,这里直接又把new的节点指向原节点的头节点?

                    • avatar SmallRubbish 来自天朝的朋友 QQ浏览器 Windows 10 广西来宾市 电信 0

                      @alex 博主您好,第三部分拆分复杂链表的if语句判断和while判断,这样一前一后的作用是什么。我怎么分析的这两个语句的结构都是原链表啊,好迷啊