• Leetcode 138
• Difficulty: Medium

---

Problem Definition

Given a linked list where each node contains a next pointer and an arbitrary pointer to any other node, write a function to deep copy the linked list.

---

Node Class

Below is the Node class that will represent elements in the linked list.

class Node:
    def __init__(self, value: int, next: 'Node' = None, random: 'Node' = None):
        self.value = value
        self.next = next
        self.random = random

---

Examples

Some test cases to verify our solution.

five = Node(5)
four = Node(4, next=five)
three = Node(3, next=four)
two = Node(2, next=three)
one = Node(1, next=two)
zero = Node(0, next=one)

five.random = one
four.random = zero
three.random = five
two.random = four
one.random = zero

exp = [(0, 1, None), (1, 2, 0), (2, 3, 4), (3, 4, 5), (4, 5, 0), (5, None, 1)]
head = deep_copy(zero)
res = []
while head is not None:
    next = head.next.value if head.next is not None else None
    random = head.random.value if head.random is not None else None
    res.append((head.value, next, random))
    head = head.next
assert res == exp

---

Dictionary Solution

We will build the copy linked list and maintain 2 dictionaries, one mapping the original item to its copy and one mapping the copy of an item to the item's random pointer. We will then use these 2 maps to fill in the random pointers for the items in the copy linked list.

def deep_copy(root: Node) -> Node:
    if root is None:
        return None
    head = root
    new_head = Node(head.value)
    prev = new_head
    copy_to_rand = {hash(new_head): hash(head.random)}
    orig_to_copy = {hash(head): new_head}
    while head.next is not None:
        head = head.next
        new_node = Node(head.value)
        prev.next = new_node
        copy_to_rand[hash(new_node)] = hash(head.random)
        orig_to_copy[hash(head)] = new_node
        prev = new_node
    head = new_head
    while head is not None:
        head.random = orig_to_copy.get(copy_to_rand[hash(head)], None)
        head = head.next
    return new_head

---

Dictionary Solution Complexity

Let $n = $ the number of nodes in the original linked list.

Runtime complexity should be $\Theta(n)$ since we are traversing through the list and its copy once each.

Auxiliary space complexity should be $\Theta(n)$ since we are storing 2 dictionaries of size $n$.

---

Interleaving Pointers Solution

We can reduce auxiliary space complexity by removing the need for the dictionaries.

We will interleave the originals and copies on our first loop. In our second loop, we'll use the random pointers on the originals to set the random pointers on the copies. In our third loop, we'll separate the original and copy linked lists.

def deep_copy(root: Node) -> Node:
    if root is None:
        return None
    ans = Node(value=root.value)
    curr = root.next
    root.next = ans
    ans.next = curr
    while curr is not None:
        copy = Node(value=curr.value)
        tmp = curr.next
        curr.next = copy
        copy.next = tmp
        curr = tmp
    curr = root
    while curr is not None:
        if curr.random is not None:
            curr.next.random = curr.random.next
        curr = curr.next.next
    curr = root
    prev_copy = None
    while curr is not None:
        curr_copy = curr.next
        curr.next = curr.next.next
        if prev_copy is not None:
            prev_copy.next = curr_copy
        curr = curr.next
    return ans

---

Interleaving Pointers Solution Complexity

Let $n = $ the number of nodes in the linked list.

Runtime complexity should be $\Theta(n)$.

Auxiliary space complexity should be $O(1)$.