Back to DSA

Copy List with Random Pointer

hard
Acceptance: 43%
Linked List

A linked list is given in which each node has, in addition to a normal next pointer, a random pointer that can reference any node in the list or be null. Create a complete deep copy of this list. The new list must be structurally identical — each copied node's random pointer must reference the corresponding copied node, not the original.

Examples

Example 1:
Input:head = [[3,null],[6,0],[9,2],[12,1]]
Output:[[3,null],[6,0],[9,2],[12,1]]

Hints

Related Problems

Reverse Linked ListeasyLinked List CycleeasyPalindrome Linked ListeasyMerge Two Sorted ListsmediumRemove Nth Node From End of Listmedium
00:00
import java.util.*;

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Map<Node, Node> map = new HashMap<>();
        Node curr = head;
        while (curr != null) {
            map.put(curr, new Node(curr.val));
            curr = curr.next;
        }
        curr = head;
        while (curr != null) {
            map.get(curr).next = map.get(curr.next);
            map.get(curr).random = map.get(curr.random);
            curr = curr.next;
        }
        return map.get(head);
    }
}
Time complexityO(n)
Space complexityO(n)