随机链表的复制

原题链接

使用的方法

哈希表

解题思路

• 首先，创建一个哈希表 map，用于存储原链表中每个节点与其对应的新节点之间的映射关系。
• 然后，使用一个指针 cur 遍历原链表，对于每个节点 cur，在哈希表中创建一个新的节点 newNode，并将 cur 作为键，newNode 作为值存储在哈希表中。
• 接下来，重新遍历原链表，对于每个节点 cur，通过哈希表获取对应的新节点 newNode，并设置 newNode 的 next 和 random 指针。
• 具体来说，newNode.next 应该指向 map.get(cur.next)，而 newNode.random 应该指向 map.get(cur.random)。
• 最后，返回哈希表中原链表头节点对应的新节点 map.get(head)，即复制后的链表头节点。

代码实现

/*
// 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;
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        // 第一次遍历，创建节点
        while(cur != null){
            map.put(cur,new Node(cur.val));
            cur = cur.next;
        }
        // 第二次遍历，设置新节点的next 和 random
        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);
    }
}