0138.Copy List with Random Pointer

Link: 138. Copy List with Random Pointer
Track: Amazon Tag

Question

Restate

Edge Case

• head = None
• duplicate vale

---

Method 1 - hashmap Space: O(n)
Method 2 - interleave Space: O(1)

Method 1 - hashmap

Approach

(discussed at lease two approach?)

Complexity

• Time Complexity: O(n)
• Space Complexity: O(n)

Code

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
 
        dic = {}
 
        # 1) create all nodes
        cur = head
        while cur:
            dic[cur] = Node(cur.val)
            cur = cur.next
 
        # 2) connect next/random
        cur = head
        while cur:
            dic[cur].next = dic.get(cur.next)      # None if cur.next is None
            dic[cur].random = dic.get(cur.random)  # None if cur.random is None
            cur = cur.next
 
        return dic[head]
 

Method 2 - Interleave

Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)
  • auxiliary sort

Code

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None
 
        # 1) Interleave: A -> A' -> B -> B' -> C -> C'
        cur = head
        while cur:
            clone = Node(cur.val)
            clone.next = cur.next
            cur.next = clone
            cur = clone.next  # move to next original node
 
        # 2) Set random for clones:
        # If original cur.random = X, then clone cur.next.random = X'
        # and X' is X.next (because of interleaving)
        cur = head
        while cur:
            clone = cur.next
            if cur.random:
                clone.random = cur.random.next
            else:
                clone.random = None
            cur = clone.next  # move to next original node
 
        # 3) Separate the two lists:
        # restore original and extract cloned list
        cur = head
        clone_head = head.next
        while cur:
            clone = cur.next
            next_original = clone.next
 
            # restore original next
            cur.next = next_original
 
            # set clone next
            if next_original:
                clone.next = next_original.next
            else:
                clone.next = None
 
            cur = next_original
 
        return clone_head

---

History

• Jan-xx-2026 Peeked