138. 复制带随机指针的链表

138. 复制带随机指针的链表 (opens new window)

该题同

剑指 Offer 35. 复杂链表的复制 (opens new window)

解法一

1. 使用一个map做映射，记录原链表节点对应的新链表节点
2. 直接while遍历链表，并且查看map中是否有当前节点对应的新节点的映射存在（因为random节点的原因，可能会提前记录好后面节点的映射关系），若没有，新建一个，并放入map中记录好。
3. 由于random指针同样是指向链表中的某个节点，所以遍历时，每次从map中获取是否已经遍历过对应的映射节点了，若没有，就新建一个，并放入map中记录好映射关系。

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
        Node sentinel = new Node(-1);
        Node copy = sentinel;
        while (head != null) {

            Node copyHead = map.getOrDefault(head, new Node(head.val));
            map.put(head, copyHead);
            
            Node random = head.random;
            Node copyRandom = null;
            if (random != null) {
                copyRandom = map.getOrDefault(random, new Node(random.val));
                map.put(random, copyRandom);
            }
            copyHead.random = copyRandom;
            
            head = head.next;

            copy.next = copyHead;
            copy = copyHead;
        }
        return sentinel.next;
    }
}