35.复杂链表的复制

raylan.chen大约 2 分钟

做题时的想法：

从头开始遍历链表，遇到还未建立的 random 节点，就先创建新节点，并且拿个容器装起来，等遍历到了该节点再从容器中拿出来，拿什么装好呢？就拿 HashMap 吧，等会可以通过 Node 节点的 val 直接找到容器中的节点，然后就搁那瞎写代码

想法存在很多问题，例如通过 key: value => Node.val: new Node() 来存储新建立的 random 节点，可能存在 val 相同的情况，也就是 key 相同

还有就是如果 random 指向已建立的节点又该怎么处理呢？

优秀题解

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();
        // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        while(cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        // 4. 构建新链表的 next 和 random 指向
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        // 5. 返回新链表的头节点
        return map.get(head);
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof/solutions/476617/jian-zhi-offer-35-fu-za-lian-biao-de-fu-zhi-ha-xi-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

拿 HashMap 来存储（老：新）节点的映射，这也太秒了吧！

先遍历一遍链表，根据老节点复制新节点的 val 并且将新节点全放到 map 里面，并且做（老节点：新节点）的映射

这样，想要找到某一新节点，通过老节点映射到新节点，然后通过老节点的 random 映射到新 random 节点，随后做赋值即可

35.复杂链表的复制

35.复杂链表的复制

参考链接

个人尝试（❌）

优秀题解