🍑每一个结点有三个属性：
🍑链表的样子大概是这样：
注意这里我们复制的结点是引用类型，即我们复制的不只是结点的地址，我们需要复制的是旧结点。
比如一个这样的原链表
我们的复制不是又生成一个和上面一模一样的链表出来，我们复制的是有着原来链表结构的新的链表
新的链表的每个结点所对应的值可能和原来链表的值相同，但next和random的肯定是不同的（但所对应的关系是相同的）
为了在新链表中持和原来链表中各个结点的对应关系，我们需要用Map来记录
比如上图中
代码展示：
/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */ class Solution { public Node copyRandomList(Node head) { if (head == null) { return null; } Node cur = head; Map<Node, Node> map = new HashMap<>(); // 如果用TreeMap里面放的元素一定是可比较的,只能用HashMap // 构建新旧结点的键值对关系，旧结点是Key,新结点是Value while (cur != null) { Node tmp = new Node(cur.val); // 构造新结点tmp,旧结点是cur map.put(cur, tmp); cur = cur.next; } cur = head; // 按旧链表的结点对应关系构建新的结点，注意我们是深拷贝——即非引用类型可以直接把值拷贝出来，但对于引用类型我们拷贝的不只是地址值，还有该引用所对应的结点 while(cur != null) { map.get(cur).next = map.get(cur.next); map.get(cur).random = map.get(cur.random); cur = cur.next; } return map.get(head); // 我们要返回的是新结点的head---及key(head) 所对应的 value值是map.get(head) } }
