138. Copy List with Random Pointer

Problem¶

Given a linked list whose nodes have next and random pointers, return a deep copy preserving both pointer relationships; no copied pointer may reference an original node.

Input:  [[7, null], [13, 0], [11, 1]]
Output: [[7, null], [13, 0], [11, 1]]
State:  copy[i] is not original[i] for every i

Key trick¶

Insert each copy immediately after its original node, making the copy of any node accessible through original.next; then assign random pointers and separate the lists.

Trap¶

random can point forward, backward, to the same node, or to None.
Copying random directly creates references to original nodes.
The interleaving approach must restore the original list while separating the copy.
The empty list must return None.

Why is it interesting?¶

It tests pointer manipulation and uses the list itself as an implicit original-to-copy mapping, avoiding a hash map.

Python solution¶

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

        # Insert each copy immediately after its original node.
        cur = head
        while cur:
            node = Node(cur.val)
            node.next = cur.next
            cur.next = node
            cur = node.next

        # The copy of any original random target is target.next.
        cur = head
        while cur:
            node = cur.next
            node.random = cur.random.next if cur.random else None
            cur = node.next

        # Restore the original list and extract the copied list.
        copy_head = head.next
        cur = head

        while cur:
            node = cur.next
            cur.next = node.next
            node.next = node.next.next if node.next else None
            cur = cur.next

        return copy_head

Time complexity: \(O(n)\).

Auxiliary space complexity: \(O(1)\), excluding the returned nodes.

Comment on my solution¶

Your solution is correct and handles forward, backward, and self-referencing random pointers.

Time complexity is \(O(n)\).
Space complexity is \(O(n)\).
Using id(cur) works, but mapping original node objects directly to copies is clearer.
randoms and deferred lists add complexity; a conventional hash-map solution can create all copies in one pass and connect both pointers in a second pass.
The interleaving solution above removes both maps and achieves \(O(1)\) auxiliary space.

from collections import defaultdict

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        # - you can't wire to a node you haven't built yet
        # - in .random point to a previous node, wire it
        #   - if it don't add in a map index -> list of nodes whose .random point to node index
        # - note that .random can point to itself

        if head is None:
            return None

        randoms = defaultdict(list) # id (in original list) -> new nodes
        copies = {} # id (in original list) -> copied node
        dummy = Node(0)
        tail = dummy
        cur = head # original list

        while cur:
            node = Node(cur.val)
            copies[id(cur)] = node
            tail.next = node
            tail = tail.next
            if cur.random is not None:
                randoms[id(cur.random)].append(node)
            cur = cur.next

        for original_id, copied_node in copies.items():
            for node in randoms[original_id]:
                node.random = copied_node

        return dummy.next