剑指 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 进行观看，由于视频内容对服务器的流量消耗太大，所以做了登录处理，登录后签到就可以看啦~

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

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