Copy List with Random Pointer | Leetcode 138

Welcome to our deep dive on Copy List with Random Pointer (Leetcode 138). Cloning a standard Linked List is incredibly easy (copy = new Node(curr.val)). The immense difficulty in this problem lies strictly with the newly introduced random pointer variable, which can randomly point mathematically anywhere, including to nodes we haven't even physically created yet!

Problem Statement

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.

Note: Return the head of the copied linked list.

Example: head = [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]

Approach 1: Two-Pass HashMap Caching O(N) Space

If a random pointer statically points natively at a raw Node [1], how do we know mathematically which new [1] clone node we correspond to?

We can map every Single Old Node directly to its structurally isolated Clone using a Dictionary (HashMap)!

• Old Node [Memory 0x01] -> New Clone Node [Memory 0x99]

1. Pass 1: Iterate aggressively through the original array. For every single Old Node, immediately fabricate the pure New Clone Node (just containing the integer val). Register the { Old : New } mapping mathematically inside our map.
2. Pass 2: Iterate identically again! Now, for every single Old Node, configure its structurally cloned counterpart dynamically:
   • New_Node.next = Map[Old_Node.next]
   • New_Node.random = Map[Old_Node.random]

"""
# 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
        
        # Old Node Memory -> physically referencing -> New Node Memory
        oldToCopy = {}
        
        curr = head
        # Pass 1: Clone exclusively all unlinked literal Nodes 
        while curr:
            oldToCopy[curr] = Node(curr.val)
            curr = curr.next
            
        curr = head
        # Pass 2: Iteratively bind completely isolated clone nodes dynamically!
        while curr:
            copy = oldToCopy[curr]
            # Bind the strictly cloned references mathematically extracted safely from dictionary cache
            copy.next = oldToCopy.get(curr.next)
            copy.random = oldToCopy.get(curr.random)
            curr = curr.next
            
        return oldToCopy[head]

Complexity Analysis

Approach 2: Interweaving Method O(1) Space

Can we bypass the massive O(N) Dictionary caching natively? Yes mathematically! Instead of caching "Old Node points to Clone Node" in an external map... we literally surgically inject the clones mathematically physically BETWEEN the original node strands!

We modify A -> B -> C geometrically to A -> A' -> B -> B' -> C -> C'.

Because the clone A' conceptually exists strictly physically identically bounded as A.next, assigning the random pointer bounds dynamically natively is trivial! A'.random inherently belongs directly mathematically isolated natively mapping cleanly to A.random.next!

1. Merge new clones identically inside original linked geometry mapping functionally sequentially adjacent.
2. Pass completely to bind random references exclusively on clone nodes (relying structurally dynamically over their identical original sequence bounds preceding them native inherently)!
3. Un-weave dramatically returning the separated dynamic structure natively identically identical to start bounds!

graph LR
    A["Orig A"] -.->|"1. clone into"| B["Clone A'"]
    B -.-> C["Orig B"]
    C -.->|"clone into"| D["Clone B'"]
    
    A ---->|Orig rndm| C
    B ====>>|"2. mathematically derived ->rndm"| D
    
    style B fill:#FF9800,stroke:#fff,stroke-width:2px,color:#fff
    style D fill:#FF9800,stroke:#fff,stroke-width:2px,color:#fff

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head: return None
        
        # 1. Interweave Native Clone String mathematically sequentially inside Original Geometry!
        curr = head
        while curr:
            clone = Node(curr.val, curr.next)
            curr.next = clone
            # Increment safely strictly bypassing to next pure structural original Node dynamically
            curr = clone.next
            
        # 2. Iterate evaluating structural Random bounds relying strictly recursively natively!
        curr = head
        while curr:
            if curr.random:
                # Core algorithm optimization trick natively bounds mapping identically isolated!
                curr.next.random = curr.random.next
            curr = curr.next.next
            
        # 3. Disconnect geometrically disentangling Native Original cleanly returning isolated new String natively
        curr = head
        clone_head = head.next
        
        while curr:
            clone = curr.next
            
            # Mend Native original structural loop
            curr.next = clone.next
            
            # Isolate Clone identically cleanly bounding 
            if clone.next: clone.next = clone.next.next
            
            curr = curr.next
            
        return clone_head

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (138)