DX's Digital Garden

11.深拷贝(next和random)

2 min read

  • 2.11

    • node 不用 new，而是直接从 map 的 get 方法

  • 1.24

    • node = map。get（ptr）

  • 1.20

    • 第二次做，有点理解了，
      • 第一步 put 时，put 的是新旧节点的对应关系
      • 第二步 get 时，是以旧节点知道的他们下一个 next 或者 random 指针指向的那个节点为 key，来搜索新节点的，比如A 节点的 next 是 B 节点，A.next=？-》B，然后找出 map 中的 B 节点来连接

  • 11.10

    • 用hashMap时,又忘了new,map第一次put(cur,new Node(cur.val))
    • 第二次在循环中不停生成new Node(不知道怎么复制到map里的)

  • 考的映射关系的思想,打小抄

  • 这个算法的意义在于： • 它展示了如何利用哈希映射来管理复杂对象之间的引用关系； • 是“深拷贝对象”这类问题的通用思想模板； • 不是靠语法，而是靠“映射 + 哈希表 + 两阶段构造”的算法思想。

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
 
        // 第一次遍历：复制节点，**只复制值，不处理指针**
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.val));  // old -> new映射关系
            cur = cur.next;
        }
 
        // 第二次遍历：复制 next 和 random 指针
        cur = head;
        while (cur != null) {
            Node newNode = map.get(cur);
            newNode.next = map.get(cur.next);       // 找到 old.next 对应的新节点
            newNode.random = map.get(cur.random);   // 找到 old.random 对应的新节点
            cur = cur.next;
        }
 
        return map.get(head); // 返回复制链表的头节点
    }
}
  • 第一次只做对应,而且新节点不会包含两个指针
  • 第二次才会保存指针

Graph View