Problem Description

You are given the head of a linked list of length n. Unlike a singly linked list, each node contains an additional pointer random, which may point to any node in the list, or null.

Create a deep copy of the list.

The deep copy should consist of exactly n new nodes, each including:

• The original value val of the copied node
• A next pointer to the new node corresponding to the next pointer of the original node
• A random pointer to the new node corresponding to the random pointer of the original node

Note: None of the pointers in the new list should point to nodes in the original list.

Return the head of the copied linked list.

In the examples, the linked list is represented as a list of n nodes. Each node is represented as a pair of [val, random_index] where random_index is the index of the node (0-indexed) that the random pointer points to, or null if it does not point to any node.

Example 1:

Input: head = [[3,null],[7,3],[4,0],[5,1]]
Output: [[3,null],[7,3],[4,0],[5,1]]

Example 2:

Input: head = [[1,null],[2,2],[3,2]]
Output: [[1,null],[2,2],[3,2]]

Constraints:

• 0 <= n <= 100
• -100 <= Node.val <= 100
• random is null or is pointing to some node in the linked list.

Approach

Use a HashMap to map each original node to its corresponding newly created copy node (with the same value).

1. Make a first pass through the original linked list, creating a new node for each original node and storing the mapping <OriginalNode, NewNode> in the HashMap.
2. Make a second pass through the original linked list. For each original node, use the HashMap to retrieve its corresponding new node. Set the new node’s next and random pointers to point to the mapped copies of the original node’s next and random nodes, respectively.
3. Return the mapped head node from the HashMap.

Solution

/*
// 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) {
        Node temp = head;
        HashMap<Node, Node> hash = new HashMap<>();
        while(temp!=null){
            hash.put(temp, new Node(temp.val));
            temp = temp.next;
        }
        temp = head;
        while(temp!=null){
            Node newNode = hash.get(temp);
            newNode.next = hash.get(temp.next);
            newNode.random = hash.get(temp.random);

            temp = temp.next;
        }
        return hash.get(head);
    }
}