leetcode 138. Copy List with Random Pointer | 138. 复制带随机指针的链表（复杂链表的复制）

朴灿烈づ我的快乐病毒、 2022-08-31 09:55 101阅读 0赞

## 题目 ##

[https://leetcode.com/problems/copy-list-with-random-pointer/][https_leetcode.com_problems_copy-list-with-random-pointer]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

## 题解 ##

复杂链表的复制，经典问题，考察与 HashMap 的结合。注意如果是 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;
    
            HashMap<Node, Node> map = new HashMap<>();
            map.put(null, null);
    
            Node cur = head;
            Node pre = new Node(-1);
            while (cur != null) { 
                if (!map.containsKey(cur.random)) { 
                    map.put(cur.random, new Node(cur.random.val));
                }
                if (!map.containsKey(cur)) { 
                    map.put(cur, new Node(cur.val));
                }
                Node copy = map.get(cur);
                copy.random = map.get(cur.random);
                map.put(cur, copy);
                pre.next = copy;
    
                pre = copy;
                cur = cur.next;
            }
            return map.get(head);
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_copy-list-with-random-pointer]: https://leetcode.com/problems/copy-list-with-random-pointer/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20220829/54742cd13f294c14a25c30950a295ea3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20220829/bc031a1996704cd6ba5f8a390bffb253.png