复制带随机指针的链表（ LeetCode 138 ）

题目描述

请实现 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 。

吴师兄的思路

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

• 值为 val

• 一个指向下一个节点的指针 next

• 一个指向随机节点的指针 random

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

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

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

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

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

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

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

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

吴师兄的参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 复制带随机指针的链表（ LeetCode 138 ）:https://leetcode-cn.com/problems/copy-list-with-random-pointer
class Solution {
    public Node copyRandomList




    
(Node head) {
        // 边界判断，一般链表的题目都需要判断头节点是否为空
        if(head == null) return null;

        // 从链表的头节点开始遍历
        Node cur = head;

        // 使用一一对应的哈希表结构 Map 存放已经创建的节点
        Map 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 ) {

            // 原链表节点 ----  新链表节点
            // key      ----- value
            // cur      ----- map.get(cur)

            // 0、在字典中找到一个 cur 为 key 对应的那个 value 值
            Node valueCur = map.get(cur);

            // 接下来，需要去寻找 valueCur 的 next 节点和 random 节点

            // 寻找 valueCur 的 next 节点
            // 1、获取当前节点 cur 在原链表中的 next 指针指向的节点
            Node keyNextNode = cur.next;

            // 2、在字典中找到以 keyNextNode 为 key 对应的那个 value 值
            Node valueNextNode = map.get(keyNextNode);

            // 3、那么新链表中的这个节点的 next 指针就是 valueNextNode
            valueCur.next = valueNextNode;

            // 寻找 valueCur 的  节点
            // 1、获取当前节点 cur 在原链表中的 random 指针指向的节点
            Node keyRandomNode = cur.random;

            // 2、在字典中找到以 valueRandomNode 为 key 对应的那个 value 值
            Node valueRandomNode = map.get(keyRandomNode);

            // 4、那么新链表中的这个节点的 next 指针就是 valueNextNode
            valueCur.random = valueRandomNode;


            //遍历下去，查看下一个节点
            cur = cur.next;

        }
        // 原链表节点 ----  新链表节点
        // key      ----- value
        // cur      ----- map.get(cur)
        // head     ----- map.get(head)
        return map.get(head);
    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 复制带随机指针的链表（ LeetCode 138 ）:https://leetcode-cn.com/problems/copy-list-with-random-pointer
class Solution {
public:
    Node* copyRandomList(Node* head) {
        // 边界判断，一般链表的题目都需要判断头节点是否为空
        if(head == NULL) return NULL;

        // 从链表的头节点开始遍历
        Node* cur = head;

        // 使用一一对应的哈希表结构 Map 存放已经创建的节点
        unordered_map map;

        // 遍历原链表
        while( cur != NULL ) {
            // 以原链表的节点为 Key，构建一个 Map
            // Map 的 Value 为一个新链表中的节点
            // 新节点的值 val 和原链表的值 val 一样
            // 但原链表中的每个节点都有 next 和 random 指针，而 Map 中的 Value 没有 next 和 random 指针
            // map.put(Key,Value)
            Node *newNode = new Node(cur->val);

            map[cur] = newNode;

            // 查看下一个节点的情况
            cur = cur->next;
        }

        // 再次从链表的头节点开始遍历
        cur = head;

        // 遍历原链表
        while( cur != NULL ) {

            // 原链表节点 ----  新链表节点
            // key      ----- value
            // cur      ----- map.[cur]

            // 0、在字典中找到一个 cur 为 key 对应的那个 value 值
            Node* valueCur = map[cur];

            // 接下来，需要去寻找 valueCur 的 next 节点和 random 节点

            // 寻找 valueCur 的 next 节点
            // 1、获取当前节点 cur 在原链表中的 next 指针指向的节点
            Node* keyNextNode = cur->next;

            // 2、在字典中找到以 keyNextNode 为 key 对应的那个 value 值
            Node* valueNextNode = map[keyNextNode];

            // 3、那么新链表中的这个节点的 next 指针就是 valueNextNode
            valueCur->next = valueNextNode;

            // 寻找 valueCur 的  节点
            // 1、获取当前节点 cur 在原链表中的 random 指针指向的节点
            Node* keyRandomNode = cur->random;

            // 2、在字典中找到以 valueRandomNode 为 key 对应的那个 value 值
            Node* valueRandomNode = map[keyRandomNode];

            // 4、那么新链表中的这个节点的 next 指针就是 valueNextNode
            valueCur->random = valueRandomNode;


            //遍历下去，查看下一个节点
            cur = cur->next;

        }
        // 原链表节点 ----  新链表节点
        // key      ----- value
        // cur      ----- map[cur]
        // head     ----- map[head]
        return map[head];
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解