复制带随机指针的链表( 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<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 ) {

            // 原链表节点 ----  新链表节点
            // 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<Node*, Node*> 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 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 复制带随机指针的链表( LeetCode 138 ): https://leetcode-cn.com/problems/copy-list-with-random-pointer
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
       # 边界判断,一般链表的题目都需要判断头节点是否为空
        if head == None :
           return None

        # 从链表的头节点开始遍历
        cur = head

        # 使用一一对应的哈希表结构 Map 存放已经创建的节点
        map = dict()

        # 遍历原链表
        while cur != None :
            # 以原链表的节点为 Key,构建一个 Map
            # Map 的 Value 为一个新链表中的节点
            # 新节点的值 val 和原链表的值 val 一样
            # 但原链表中的每个节点都有 next 和 random 指针,而 Map 中的 Value 没有 next 和 random 指针
            new_node = Node(cur.val,None,None)

            map[cur] = new_node

            # 查看下一个节点的情况
            cur = cur.next


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

        # 遍历原链表
        while cur != None :

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

            # 0、在字典中找到一个 cur 为 key 对应的那个 value 值

            valueCur = map.get(cur)

            # 接下来,需要去寻找 valueCur 的 next 节点和 random 节点

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

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

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

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

            # 2、在字典中找到以 valueRandomNode 为 key 对应的那个 value 值
            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)

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注