复制带随机指针的链表(中等难度)

• 题目概述(简单难度)
• 思路与代码
• • 思路展现
  • 代码示例
• 总结

题目链接：
复制带随机指针的链表

这个题目的意思就是我们的链表的每个节点不仅仅有一个next域，next域存储的下一个节点的地址，还有我们的random域，这个random域是随机的，意思就是这个域内存储的下一个节点的地址我们也不知道是哪个节点，random域可以为空，也可以不为空(存储非自身节点的某个节点的地址)，也可以存储自己节点本身的地址,所以说当我们复制这个链表的时候，就需要将next域和我们的random域一起复制过去，并且不能发生改变，此时我们就需要仔细想想要怎么复制了，这块我们巧用我们的map集合，使用Map集合来存储我们的原链表和复制后的链表的地址.如下图所示：

所以这道题目的思路就非常明了了:

关于第二点的核心语句为：

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) {
            return null;
        }
        Node cur = head;
        HashMap map = new HashMap<>();
        
        while(cur!=null) {
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        }
        //cur == null  说明第一遍历结束了   map当中存储了映射关系

        //让cur此时重新指向链表的头节点
        cur = head;

        
        while(cur!=null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
       //cur再次为空 此时说明 新的；链表的next和random已经维护完成

        //最后返回新链表的头节点
        return map.get(head);
    }
}

时间复杂度:O(N)：N为链表长度
空间复杂度:O(N)：N为链表长度