7.8 Copy List with Random Pointer

7.8.1 Problem Metadata

7.8.2 Description

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.

7.8.3 Examples

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

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

7.8.4 Constraints

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

7.8.5 Solution - HashMap (Two-Pass)

7.8.5.1 Walkthrough

This solution uses a HashMap to store the mapping between original nodes and their cloned counterparts, enabling easy lookup when setting random pointers.

Two-Pass Strategy:

  1. Pass 1 - Clone nodes and build next pointers:
    • Traverse the original list
    • For each node, create a clone with the same value
    • Build the next pointer chain for the cloned list
    • Store the mapping: original → clone in a HashMap
  2. Pass 2 - Set random pointers:
    • Traverse the original list again
    • For each node, use the HashMap to find its clone and the clone of its random target
    • Set clonedNode.random = HashMap.get(originalNode.random)

Why This Works: The HashMap allows O(1) lookup of any cloned node when we need to set random pointers. By separating the process into two passes, we ensure all nodes exist before we start connecting random pointers.

Example: Copy A → B → C where A.random → C, B.random → A:

Pass 1: Create nodes and next pointers
        Original: A → B → C
        Clone:    A' → B' → C'
        HashMap:  {A: A', B: B', C: C'}

Pass 2: Set random pointers using HashMap
        A.random = C  →  A'.random = HashMap.get(C) = C'
        B.random = A  →  B'.random = HashMap.get(A) = A'

Result: A' → B' → C' with correct random pointers

7.8.5.2 Analysis

  • Time Complexity: O(n) - Two passes through the list
  • Space Complexity: O(n) - HashMap stores n node mappings
  • Trade-off: Uses extra space but more intuitive and easier to implement

7.8.5.3 Implementation Steps

  1. Handle edge case: if head is null, return null.
  2. First pass:
    • Create cloned nodes one by one
    • Build the next pointer chain
    • Store mapping in HashMap
  3. Second pass:
    • For each original node, get its clone from HashMap
    • Get the clone’s random target from HashMap
    • Set the clone’s random pointer
  4. Return the cloned list’s head.

7.8.5.4 Code - Java

public Node copyRandomList(Node head) {
    if (head == null) {
        return head;
    }

    // Mapping of original nodes to clone nodes
    Map<Node, Node> nodeMap = new HashMap<>();

    Node curr = head;
    Node cloneHead = null;
    Node clonePrev = null;

    // Create cloned linked list nodes without random pointer
    while (curr != null) {
        Node cloneCurr = new Node(curr.val);
        nodeMap.putIfAbsent(curr, cloneCurr);

        if (clonePrev == null) {
            cloneHead = cloneCurr;
        } else {
            clonePrev.next = cloneCurr;
        }
        clonePrev = cloneCurr;

        curr = curr.next;
    }

    // Traverse again to set random pointer to cloned linked list
    curr = head;
    while (curr != null) {
        Node origRand = curr.random;
        Node cloneCurr = nodeMap.get(curr);
        Node cloneRand = nodeMap.get(origRand);
        cloneCurr.random = cloneRand;

        curr = curr.next;
    }

    return cloneHead;
}

7.8.5.5 Code - Golang

func copyRandomList(head *Node) *Node {
    if head == nil {
        return head
    }

    // Mapping of original nodes to clone nodes
    nodeMap := make(map[*Node]*Node)

    curr := head
    var cloneHead *Node
    var clonePrev *Node
    var cloneCurr *Node

    // Create cloned linked list nodes without random pointer
    for curr != nil {
        cloneCurr = &Node{Val: curr.Val}
        nodeMap[curr] = cloneCurr

        if clonePrev == nil {
            cloneHead = cloneCurr
        } else {
            clonePrev.Next = cloneCurr
        }

        clonePrev = cloneCurr
        curr = curr.Next
    }

    var cloneRand *Node
    curr = head
    // Traverse again to set random pointer to cloned linked list
    for curr != nil {
        origRand := curr.Random
        cloneCurr = nodeMap[curr]
        cloneRand = nodeMap[origRand]
        cloneCurr.Random = cloneRand

        curr = curr.Next
    }

    return cloneHead
}

7.8.6 Solution - Interleaving Nodes (Space Optimized)

7.8.6.1 Walkthrough

This solution achieves O(1) space by interleaving copied nodes with original nodes, then separating them.

Three-Pass Strategy:

  1. Pass 1 - Interleave: Insert each copy right after its original
    • A → B → C becomes A → A' → B → B' → C → C'
  2. Pass 2 - Set random pointers: For each original node, set its copy’s random
    • copy.random = original.random.next (the copy of random target)
  3. Pass 3 - Separate: Extract copied nodes into their own list

Why This Works: By placing each copy adjacent to its original, we can find any random target’s copy in O(1) by looking at original.random.next.

Example: Copy A → B → C where A.random → C, B.random → A:

Pass 1: A → A' → B → B' → C → C'

Pass 2: A.random = C, so A'.random = C.next = C'
        B.random = A, so B'.random = A.next = A'

Pass 3: Separate into A → B → C and A' → B' → C'

7.8.6.2 Analysis

  • Time Complexity: O(n) - Three passes through the list
  • Space Complexity: O(1) - No extra data structures (copies don’t count as auxiliary space)

7.8.6.3 Implementation Steps

  1. Pass 1: For each node, create copy and insert after original.
  2. Pass 2: For each original, set original.next.random = original.random.next.
  3. Pass 3: Separate the interleaved list into original and copy lists.
  4. Return the head of the copy list.

7.8.6.4 Code - Java

public Node copyRandomList(Node head) {
    if (head == null) return null;
    for (Node curr = head; curr != null; curr = curr.next.next) {
        Node copy = new Node(curr.val);
        copy.next = curr.next;
        curr.next = copy;
    }
    for (Node curr = head; curr != null; curr = curr.next.next) {
        if (curr.random != null) {
            curr.next.random = curr.random.next;
        }
    }
    Node pseudoHead = new Node(0);
    Node copyCurr = pseudoHead;
    Node curr = head;
    while (curr != null) {
        copyCurr.next = curr.next;
        curr.next = curr.next.next;
        curr = curr.next;
        copyCurr = copyCurr.next;
    }
    return pseudoHead.next;
}