Copy List With Random Pointer

Problem 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. 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 the value of the node.
• 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.

Examples

Constraints

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

Node Interweaving to Avoid Hash Maps

While mapping original nodes to cloned nodes in a hash map takes O(n) space, we can clone the list in O(1) auxiliary space by interweaving the cloned nodes directly into the original list.

1. Clone Nodes: Iterate through the original list. For each node, create its clone and insert the clone between the node and its original next node: original -> clone -> next_original.
2. Assign Random Pointers: Iterate through the interwoven list. For each original node curr, if it has a random pointer, the clone’s random pointer should point to the clone of curr.random: curr.next.random = curr.random.next.
3. Separate Lists: Separate the interwoven list back into the original list and the cloned list by adjusting next pointers.

Solution 1: Node Interweaving

Weave cloned nodes in place to assign random pointers without hash map memory.

/*
// 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;

        // 1. Interweave cloned nodes
        Node curr = head;
        while (curr != null) {
            Node clone = new Node(curr.val);
            clone.next = curr.next;
            curr.next = clone;
            curr = clone.next;
        }

        // 2. Assign random pointers
        curr = head;
        while (curr != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next; // points to the clone of random node
            }
            curr = curr.next.next;
        }

        // 3. Separate lists
        Node original = head;
        Node cloneHead = head.next;
        Node clone = cloneHead;

        while (original != null) {
            original.next = original.next.next;
            clone.next = (clone.next != null) ? clone.next.next : null;
            original = original.next;
            clone = clone.next;
        }

        return cloneHead;
    }
}

# Definition for a Node.
# class Node:
#     def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
#         self.val = int(x)
#         self.next = next
#         self.random = random

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None

        # 1. Interweave cloned nodes
        curr = head
        while curr:
            clone = Node(curr.val)
            clone.next = curr.next
            curr.next = clone
            curr = clone.next

        # 2. Assign random pointers
        curr = head
        while curr:
            if curr.random:
                curr.next.random = curr.random.next  # points to clone of random node
            curr = curr.next.next

        # 3. Separate lists
        original = head
        clone_head = head.next
        clone = clone_head
        
        while original:
            original.next = original.next.next
            clone.next = clone.next.next if clone.next else None
            original = original.next
            clone = clone.next
            
        return clone_head

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;

        // 1. Interweave cloned nodes
        Node* curr = head;
        while (curr) {
            Node* clone = new Node(curr->val);
            clone->next = curr->next;
            curr->next = clone;
            curr = clone->next;
        }

        // 2. Assign random pointers
        curr = head;
        while (curr) {
            if (curr->random) {
                curr->next->random = curr->random->next;
            }
            curr = curr->next->next;
        }

        // 3. Separate lists
        Node* original = head;
        Node* cloneHead = head->next;
        Node* clone = cloneHead;

        while (original) {
            original->next = original->next->next;
            clone->next = clone->next ? clone->next->next : nullptr;
            original = original->next;
            clone = clone->next;
        }

        return cloneHead;
    }
};

Complexity Analysis

• Time Complexity: O(n) since we iterate through the list three times.
• Space Complexity: O(1) auxiliary space as we do not use hash maps to store nodes.

Where It Breaks

If the original list must remain unmodified at all times (e.g. read-only list accessed by multiple threads concurrently), interweaving the nodes temporary will cause race conditions. Under those conditions, a hash map approach is required.

Common Mistakes

• Incorrect pointer separation: Separating list pointers incorrectly, which can lead to cycle loops or lose tail elements.
• Null random pointer checks: Accessing curr.random.next without checking if curr.random is null.

Frequently Asked Questions

Why does this require three loops? We need to insert all clone nodes first to ensure that when we assign random pointers, all target cloned nodes already exist in the list structure.

How does this behave with a single node? The loops will correctly duplicate the node, copy its random pointer to its clone, and separate them back to two lists.

← All Problems