专栏首页五分钟学算法剑指 Offer 35. 复杂链表的复制

剑指 Offer 35. 复杂链表的复制

额,这篇文章是昨天的头条文章,但由于自己起了一个骚的题目,导致翻车严重,没几个人看,所以起个正常的标题再发一次。

一、题目描述

请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null

示例 1:

复杂链表的复制

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

提示:

  • -10000 <= Node.val <= 10000
  • Node.random 为空(null)或指向链表中的节点。
  • 节点数目不超过 1000 。

二、题目解析

我们依旧用 四步分析法 进行结构化的分析。

  • 模拟:模拟题目的运行。
  • 规律:尝试总结出题目的一般规律和特点。
  • 匹配:找到符合这些特点的数据结构与算法。
  • 边界:考虑特殊情况。

1、模拟

对于链表中的每个节点来说,它都有三个特征:

  • 值为 val
  • 一个指向下一个节点的指针 next
  • 一个指向随机节点的指针 random

要想复制这样一个复杂链表必须要考虑到这三个特征。

如果没有 random 指针的话,那就是普通的链表,只需要遍历链表,然后每轮创建新节点,同时赋值 val 和调整前驱指针指向当前节点就行。

这题出现了 random 指针,由于它可以指向 null 、前面的节点或者后面的节点, 无法做到在一次遍历的过程中就确定下来,因为如果是指向后面的节点,但后面的节点还没有创建生成,无法确定。

所以,我们需要在一开始把所有的节点都创建出来,避免 random 找不到指向,同时观察上图,每个节点都通过 random 对应着一个新的节点,这种一一对应的关系,符合哈希表的特征。

此时的哈希表以原链表的节点作为键,新创建的节点作为值

面试题 35.复杂链表的复制完整.003

面试题 35.复杂链表的复制完整.005

原链表(Key)中的每个节点都有 next 和 random 指针,而新链表(Value) 没有 next 和 random 指针。

需要通过第二次的遍历过程进行指针指向的调整。

在第二次遍历过程中,以原链表中的节点作为键,查找当前原节点的指针指向,然后调整新节点的指针指向。

面试题 35.复杂链表的复制完整.009

2、规律

3、匹配

数据结构为链表,遍历方式使用 while 的方式。

4、边界

  • 链表为空

三、动画描述

四、图片描述

面试题 35.复杂链表的复制完整.002

面试题 35.复杂链表的复制完整.003

面试题 35.复杂链表的复制完整.004

面试题 35.复杂链表的复制完整.005

面试题 35.复杂链表的复制完整.006

面试题 35.复杂链表的复制完整.007

面试题 35.复杂链表的复制完整.008

面试题 35.复杂链表的复制完整.009

面试题 35.复杂链表的复制完整.010

面试题 35.复杂链表的复制完整.011

面试题 35.复杂链表的复制完整.012

面试题 35.复杂链表的复制完整.013

面试题 35.复杂链表的复制完整.014

面试题 35.复杂链表的复制完整.015

面试题 35.复杂链表的复制完整.016

五、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
    public Node copyRandomList(Node head) {
        // 边界判断,一般链表的题目都需要判断头节点是否为空
        if(head == null) return null;
        // 从链表的头节点开始遍历
        Node cur = head;
        // 使用一一对应的哈希表结构 Map 存放已经创建的节点
        Map<Node, Node> map = new HashMap<>();
        // 遍历原链表
        while(cur != null) {
            // 以原链表的节点为 Key,构建一个 Map, Map 的 Value 为一个新链表中的节点,新节点的值 val 和原链表的值 val 一样,但原链表中的每个节点都有 next 和 random 指针,而 Map 中的 Value 没有 next 和 random 指针
          // map.put(Key,Value)
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        // 再次从链表的头节点开始遍历
        cur = head;
        // 遍历原链表
        while(cur != null) {
            // 1、取出 Map 中 Key 为 cur 的那个节点值,即 Value 值,新节点,暂时没有 next 和 random 指针
            // 2、取出 Map 中 Key 为 cur.next 的那个节点,将其赋值给上述的 Value 的 next 指针
            // 3、取出 Map 中 Key 为 cur.random 的那个节点,,将其赋值给上述的 Value 的 random 指针   
            map.get(cur).next = map.get(cur.next);
          
            map.get(cur).random = map.get(cur.random);
            
            //遍历下去
            cur = cur.next;
        }
        // 返回结果
        return map.get(head);
    }
}

六、复杂度分析

时间复杂度

时间复杂度为 O(N)。

空间复杂度

空间复杂度为 O(N)。

七、相关标签

  • 链表

本文的所有内容我录制了视频讲解,动画制作+剪辑+配字幕花费了七八个小时,自认为讲的还算可以,感兴趣的小伙伴可以在电脑端访问 https://www.algomooc.com/354.html 进行观看,由于视频内容对服务器的流量消耗太大,所以做了登录处理,登录后签到就可以看啦~


我是程序员吴师兄,一个喜欢用图片和动画讲解算法的程序员。

以上就是本文的全部内容了,如果觉得有收获,记得点赞、再看、留言、转发,我们下期再见。

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:小吴

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-05-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【剑指Offer】35. 复杂链表的复制

    输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的 head。 请对此链表进...

    瑞新
  • 【剑指Offer】复杂链表的复制

    请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链...

    小新哟
  • 剑指offer——复杂链表的复制

    题目描述 输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注...

    AI那点小事
  • 剑指offer - 复杂链表的复制 - JavaScript

    题目描述:输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的 head。(注意...

    心谭博客
  • 剑指offer No.25 复杂链表的复制

    输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中...

    week
  • 剑指OFFER之复杂链表的复制(九度OJ1524)

    题目描述: 输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点)。 输入: 输入可能包含多个测试样例,输入以...

    用户1154259
  • 剑指Offer面试题:24.复杂链表的复制

      下图是一个含有5个结点的复杂链表。图中实线箭头表示m_pNext指针,虚线箭头表示m_pSibling指针。为简单起见,指向NULL的指针没有画出。

    Edison Zhou
  • 剑指 offer代码解析——面试题26复杂链表的复制

    本题详细解析均在代码注释中: /** * 题目:请复制一个复杂链表。每个结点除了有一个next指针指向下一个结点外,还有一个sibling指向链表中的任意一个...

    大闲人柴毛毛
  • Sword To Offer 025 - 复杂链表的复制

    输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中...

    Reck Zhang
  • [剑指offer] 复杂链表的复制

    输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中...

    尾尾部落
  • Day25:复杂链表的复制

    第一步:在原节点后面创建一个相同的节点,其实就是链表插入的过程。具体过程如下图:

    一计之长
  • 【go】剑指offer: 删除链表结点O(1)时间复杂度

    给定单链表的头指针和一个结点指针,定义一个函数在O(1)时间删除结点,链表结点与函数的定义如下:

    陌无崖
  • 剑指Offer-删除链表中重复的结点

    package LinkedList; /** * 删除链表中重复的结点 * 在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保...

    武培轩
  • 剑指offer——删除链表中重复的结点

    AI那点小事
  • 剑指offer 删除链表中的重复的结点

    在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1...

    week
  • 牛客网 复杂链表的复制

    输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中...

  • 【剑指Offer】18.2 删除链表中重复的结点

    瑞新
  • 剑指 Offer(C++版本)系列:剑指 Offer 06 从尾到头打印链表

    同步GitHub在此 ? https://github.com/TeFuirnever/GXL-Skill-Tree

    我是管小亮
  • LeetCode 138. 复制带随机指针的链表(哈希 / 深拷贝)

    给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。

    Michael阿明

扫码关注云+社区

领取腾讯云代金券