每日写题分享--复制带有随机指针的复杂链表HashMap

每日写题分享--复制带有随机指针的复杂链表/HashMap

题目描述：

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

解题思路：

1.遍历链表，利用HashMap存储老节点和新复制的节点之间的关系，即key值为老节点，val值为新结点，新结点的val==老节点的val。

2.再次遍历链表，维护每个链表之间的关系，将新链表的各个节点连接起来。

3.返回头结点。

代码实现如下：

class Solution {
    public Node copyRandomList(Node head) {
        HashMap map = new HashMap<>();//存储老节点和新节点的关系   
        Node cur = head;
        while (cur != null) {
            Node tmp = new Node(cur.val);
            map.put(cur,tmp);//一一对应，tmp为新结点
            cur = cur.next;
        }
        cur = head;//再次遍历，复制链表
        while (cur != null) {
            //新结点tmp             相当于tmp.next
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}