Problem Statement

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.
Your code will only be given the head of the original linked list.

Sample Test Cases

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Example 2:

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

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Constraints:

0 <= n <= 1000
-10^4 <= Node.val <= 10^4
Node.random is null or is pointing to some node in the linked list.

Intuition

We need to always track the next pointer, random pointer of the original node. If we create a cloned linked list, we must know or look fast in a data structure and see which is the random pointer and which is the next pointer.

Approach

Approach 1 - Using Extra Space HashMap

• Traverse through the linked list and create duplicate nodes.
• Store the original node and duplicate node into the hashmap.
• Traverse through the linked list again.
• Check which is the next pointer and random pointer of the original node. It is easier for us to see the duplicate nodes as well from the hashmap. So we can directly map the duplicate as well.
• Finally return the duplicated linked list.

Approach 2 - Store duplicate nodes in between original linked list.

• Instead of using extra space, we can use the original linked list itself.
• First we will insert duplicate nodes in between the original nodes.
• As second step, we will map the random pointer. Since we kept the duplicate nodes at the next pointers of original node, we can easily map the random pointer by adjusting the links.
• Final step is to mark the next node and extract out the final result.

Complexity

• Time complexity:

  O(lengthOfLinkedList) for both the approach.

• Space complexity:

  Without considering the final result array, hashmap based approach use O(lengthOfList) as space.
  Approach 2 uses O(1) space.

Code

Using Extra Space

/*
// 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> originalDuplicateMap = new HashMap<>();
        Node current = head;
        while (current != null) {
            Node duplicate = new Node(current.val);
            originalDuplicateMap.put(current, duplicate);
            current = current.next;
        }
        current = head;
        while (current != null) {
            Node nextNodeOfCurrent = current.next;
            Node randomNodeOfCurrent = current.random;
            Node duplicateNode = originalDuplicateMap.get(current);
            duplicateNode.next = originalDuplicateMap.get(nextNodeOfCurrent);
            duplicateNode.random = randomNodeOfCurrent == null ? null : originalDuplicateMap.get(randomNodeOfCurrent);
            current = current.next;
        }
        Node duplicateHead = originalDuplicateMap.get(head);
        return duplicateHead;
    }
}

Without using Extra Space

/*
// 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;
        }
        // insert the node in between original list nodes
        Node current = head;
        while (current != null) {
            Node duplicateNode = new Node(current.val);
            Node originalCurrentNodeNext = current.next;
            current.next = duplicateNode;
            duplicateNode.next = originalCurrentNodeNext;
            current = current.next.next;
        }

        // map the random pointers
        current = head;
        while (current != null) {
            if (current.random != null) {
                current.next.random = current.random.next;
            }
            current = current.next.next;
        }
        current = head;
        Node result = new Node(-1);
        Node finalResult = result;
        while (current != null) {
            Node copy = current.next;
            current.next = copy.next;
            finalResult.next = copy;
            finalResult = copy;
            current = current.next;
        }
        return result.next;
    }
}