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

大家好，我是程序员吴师兄，欢迎来到 图解剑指 Offer 结构化专栏，在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码，希望能帮助你即使在面试的时候紧张也能做对。

AlgoMooc 算法慕课网，每道题目都有动画和图片，致力于帮助每个程序员通过算法面试！

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题 35.复杂链表的复制。

题目汇总链接：https://www.algomooc.com/jianzhioffer

一、题目描述

请实现 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 对应着一个新的节点，这种一一对应的关系，符合哈希表的特征。

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

原链表（Key）中的每个节点都有 next 和 random 指针，而新链表（Value） 没有 next 和 random 指针。

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

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

2、规律

无

3、匹配

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

4、边界

• 链表为空

三、动画描述

四、图片描述

五、参考代码

// 登录 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)。

七、相关标签

• 链表

程序员吴师兄算法训练营永久会员

收藏 海报 链接