[LC]35. 复杂链表的复制

🚩传送门：牛客题目

题目

请实现 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 指针指向下一个节点，还有一个 指针指向链表中的任意节点或者。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

解题思路：哈希表

利用哈希表的查询特点，考虑构建 原链表节点 和 新链表对应节点 的键值对映射关系，再遍历构建新链表各节点的 和引用指向即可。

复杂度分析

时间复杂度： ，其中 是链表的长度，两轮遍历链表。

空间复杂度： ，哈希表 使用线性大小的额外空间。

我的代码

class Solution {
    public Node copyRandomList(Node head) {
        HashMap<Node, Node> map = new HashMap<Node, Node>();
        Node next = head;
        // 空指针映射关系
        map.put(null, null);
        // 建立原链表结点与新链表结点的映射关系
        while (next != null) {
            map.put(next, new Node(next.val));
            next = next.next;
        }
        next = head;
        Node newHead=map.get(next);
        Node Tail=newHead;
        // 构建 next、random
        while (next!=null){
            Tail.random=map.get(next.random);
            Tail.next=map.get(next.next);
            next=next.next;
            Tail=Tail.next;
        }
        return newHead;
    }
}