复杂链表的复制

题目

题目链接

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

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

示例 4：

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示：

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

解题思路

其实这道题就是要将链表深拷贝并获取
利用HashMap来存储节点，key是当前的节点，value代表实际的节点（拷贝之后的）

1. 将所有节点遍历并添加到hashmap中
2. 复制节点并且复制其节点指向

如图所示，表示如何复制节点以及复制指向

代码

class Solution {
    public Node copyRandomList(Node head) {
        HashMap<Node, Node> hashMap = new HashMap<Node, Node>();
        Node temp = head;
        while (temp != null) {
            //将当前节点作为key，构造新节点作为value 放入map中
            hashMap.put(temp, new Node(temp.val));
            //依次遍历
            temp = temp.next;
        }
        //准备赋值引用
        temp = head;
        while (temp != null) {
            hashMap.get(temp).next = hashMap.get(temp.next);
            hashMap.get(temp).random = hashMap.get(temp.random);
            temp = temp.next;
        }
        return hashMap.get(head);

    }
}

本文地址：https://blog.csdn.net/qq_35416214/article/details/107542549