Copy Linked List With Random Pointer (Hashmap + Interleave method)

138.Copy List with Random Pointer

Linked List

Hash Table

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. Return the head of the copied linked list.

Example:

Input:

head = [[7,null], [13,0], [11,4], [10,2], [1,0]]

→

Output:

Deep copy of the linked list

Each array element [val, random_index] indicates value and random pointer position.

Algorithm:

1. Solution 1 (Hash Map):
   • Map original nodes to their copies
   • Create new nodes while traversing
   • Link random and next pointers using the map
2. Solution 2 (Interweaving):
   • Create copy nodes and interweave with original list
   • Set random pointers for copies using interweaved structure
   • Separate the two lists

Complexity:

Hash Map Solution: Time: O(n) | Space: O(n)

Interweaving Solution: Time: O(n) | Space: O(1)

Java Solution:

// Solution 1: Hash Map Approach
public Node copyRandomListMap(Node head) {
    Map<Node, Node> map = new HashMap<>();
    Node cur = head;
    
    while (cur != null) {
        if (!map.containsKey(cur)) 
            map.put(cur, new Node(cur.val));
        
        if (cur.next != null && !map.containsKey(cur.next)) 
            map.put(cur.next, new Node(cur.next.val));
        
        if (cur.random != null && !map.containsKey(cur.random)) 
            map.put(cur.random, new Node(cur.random.val));
        
        map.get(cur).random = map.get(cur.random);
        map.get(cur).next = map.get(cur.next);
        cur = cur.next;
    }
    return map.get(head);
}

// Solution 2: Interweaving Approach (Constant Space)
// A -> A' -> B -> B' -> C -> C'
public Node copyRandomListInterweave(Node head) {
    Node iter = head, next;

    // First round: make copy of each node,
    // and link them together side-by-side in a single list.
    while (iter != null) {
        next = iter.next;
        Node copy = new Node(iter.val);
        iter.next = copy;
        copy.next = next;
        iter = next;
    }

    // Second round: assign random pointers for the copy nodes.
    iter = head;
    while (iter != null) {
        if (iter.random != null) {
            iter.next.random = iter.random.next;
        }
        iter = iter.next.next;
    }

    // Third round: restore the original list, and extract the copy list.
    iter = head;
    Node dummy = new Node(0);
    Node copy, copyIter = dummy;

    while (iter != null) {
        next = iter.next.next;
        
        // extract the copy
        copy = iter.next;
        copyIter.next = copy;
        copyIter = copy;

        // restore the original list
        iter.next = next;
        iter = next;
    }

    return dummy.next;
}

Python Solution:

# Solution 1: Hash Map Approach
def copyRandomList(self, head: 'Node') -> 'Node':
    if not head: return None
    mapping = {}
    curr = head
    
    # First pass: create copy nodes
    while curr:
        mapping[curr] = Node(curr.val)
        curr = curr.next
    
    # Second pass: assign pointers
    curr = head
    while curr:
        mapping[curr].next = mapping.get(curr.next)
        mapping[curr].random = mapping.get(curr.random)
        curr = curr.next
        
    return mapping[head]

# Solution 2: Interweaving Approach
def copyRandomList(self, head: 'Node') -> 'Node':
    if not head: return None
    curr = head
    
    # First round: create interweaved list
    while curr:
        copy = Node(curr.val)
        copy.next = curr.next
        curr.next = copy
        curr = copy.next
    
    # Second round: assign random pointers
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random.next
        curr = curr.next.next
    
    # Third round: separate lists
    curr = head
    dummy = Node(0)
    copy_curr = dummy
    
    while curr:
        # Extract copy and restore original
        next_orig = curr.next.next
        copy = curr.next
        copy_curr.next = copy
        copy_curr = copy
        curr.next = next_orig
        curr = next_orig
    
    return dummy.next

C++ Solution:

// Solution 1: Hash Map Approach
Node* copyRandomList(Node* head) {
    unordered_map<Node*, Node*> mapping;
    
    // First pass: create nodes
    Node* curr = head;
    while (curr) {
        mapping[curr] = new Node(curr->val);
        curr = curr->next;
    }
    
    // Second pass: assign pointers
    curr = head;
    while (curr) {
        mapping[curr]->next = mapping[curr->next];
        mapping[curr]->random = mapping[curr->random];
        curr = curr->next;
    }
    
    return mapping[head];
}

// Solution 2: Interweaving Approach
Node* copyRandomList(Node* head) {
    if (!head) return nullptr;
    
    // First round: create interweaved list
    Node* curr = head;
    while (curr) {
        Node* copy = new Node(curr->val);
        copy->next = curr->next;
        curr->next = copy;
        curr = copy->next;
    }
    
    // Second round: assign random pointers
    curr = head;
    while (curr) {
        if (curr->random) {
            curr->next->random = curr->random->next;
        }
        curr = curr->next->next;
    }
    
    // Third round: separate lists
    curr = head;
    Node* dummy = new Node(0);
    Node* copy_curr = dummy;
    
    while (curr) {
        Node* next_orig = curr->next->next;
        Node* copy = curr->next;
        copy_curr->next = copy;
        copy_curr = copy;
        curr->next = next_orig;
        curr = next_orig;
    }
    
    return dummy->next;
}