Difficulty: Medium · LeetCode 138

Problem

Construct a deep copy of a linked list where each node has an extra random pointer.

Understanding the problem

Deep copy requires copying nodes and setting next and random pointers correctly.

Intuition

Interleave copied nodes directly after original nodes (A -> A' -> B -> B') to set random pointers in O(1) extra space.

Approach

Pass 1: Interleave cloned nodes copy = Node(curr.val) after curr.
Pass 2: Set random pointers: curr.next.random = curr.random.next.
Pass 3: Unweave original and cloned lists.

Naive Solution — Brute Force

Use a hash map mapping original_node -> copied_node.

Python

class Solution:
    def copyRandomList(self, head):
        if not head:
            return None

        copies = {}

        current = head

        while current:
            copies[current] = Node(current.val)
            current = current.next

        current = head

        while current:
            copies[current].next = copies.get(
                current.next
            )

            copies[current].random = copies.get(
                current.random
            )

            current = current.next

        return copies[head]

C++

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

        unordered_map<Node*, Node*> copies;
        copies[nullptr] = nullptr;

        Node* current = head;

        while (current) {
            copies[current] = new Node(current->val);
            current = current->next;
        }

        current = head;

        while (current) {
            copies[current]->next = copies[current->next];
            copies[current]->random = copies[current->random];

            current = current->next;
        }

        return copies[head];
    }
};

Java

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

        Map<Node, Node> copies = new HashMap<>();

        Node current = head;

        while (current != null) {
            copies.put(current, new Node(current.val));
            current = current.next;
        }

        current = head;

        while (current != null) {
            copies.get(current).next = copies.get(current.next);
            copies.get(current).random = copies.get(current.random);

            current = current.next;
        }

        return copies.get(head);
    }
}

JavaScript

var copyRandomList = function(head) {
    if (!head) {
        return null;
    }

    const copies = new Map();

    let current = head;

    while (current) {
        copies.set(current, new _Node(current.val, null, null));
        current = current.next;
    }

    current = head;

    while (current) {
        copies.get(current).next = copies.get(current.next) || null;
        copies.get(current).random = copies.get(current.random) || null;

        current = current.next;
    }

    return copies.get(head);
};

Time: O(n) · Space: O(n)

Optimized Code (Python 3)

Python

class Solution:
    def copyRandomList(self, head):
        if not head:
            return None

        current = head

        # Create copied nodes
        while current:
            copy = Node(current.val)

            copy.next = current.next
            current.next = copy

            current = copy.next

        # Set random pointers
        current = head

        while current:
            if current.random:
                current.next.random = (
                    current.random.next
                )

            current = current.next.next

        # Separate lists
        dummy = Node(0)
        copy_current = dummy
        current = head

        while current:
            copy = current.next

            copy_current.next = copy
            copy_current = copy

            current.next = copy.next
            current = current.next

        return dummy.next

C++

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

        Node* current = head;

        // Create copied nodes
        while (current) {
            Node* copy = new Node(current->val);

            copy->next = current->next;
            current->next = copy;

            current = copy->next;
        }

        // Set random pointers
        current = head;

        while (current) {
            if (current->random) {
                current->next->random = current->random->next;
            }

            current = current->next->next;
        }

        // Separate lists
        Node dummy(0);
        Node* copyCurrent = &dummy;
        current = head;

        while (current) {
            Node* copy = current->next;

            copyCurrent->next = copy;
            copyCurrent = copy;

            current->next = copy->next;
            current = current->next;
        }

        return dummy.next;
    }
};

Java

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

        Node current = head;

        // Create copied nodes
        while (current != null) {
            Node copy = new Node(current.val);

            copy.next = current.next;
            current.next = copy;

            current = copy.next;
        }

        // Set random pointers
        current = head;

        while (current != null) {
            if (current.random != null) {
                current.next.random = current.random.next;
            }

            current = current.next.next;
        }

        // Separate lists
        Node dummy = new Node(0);
        Node copyCurrent = dummy;
        current = head;

        while (current != null) {
            Node copy = current.next;

            copyCurrent.next = copy;
            copyCurrent = copy;

            current.next = copy.next;
            current = current.next;
        }

        return dummy.next;
    }
}

JavaScript

var copyRandomList = function(head) {
    if (!head) {
        return null;
    }

    let current = head;

    // Create copied nodes
    while (current) {
        const copy = new _Node(current.val, null, null);

        copy.next = current.next;
        current.next = copy;

        current = copy.next;
    }

    // Set random pointers
    current = head;

    while (current) {
        if (current.random) {
            current.next.random = current.random.next;
        }

        current = current.next.next;
    }

    // Separate lists
    const dummy = new _Node(0, null, null);
    let copyCurrent = dummy;
    current = head;

    while (current) {
        const copy = current.next;

        copyCurrent.next = copy;
        copyCurrent = copy;

        current.next = copy.next;
        current = current.next;
    }

    return dummy.next;
};

Time: O(n) · Aux Space: O(1)

Takeaway

Pattern — Interleave copied nodes with original nodes