Chapter 7: Miscellaneous

7.1 Copy / Clone Data Structure

无论是什么数据结构，都至少需要按照对应的方法遍历一遍。如果这种数据结构包含指向另一个同类型object的指针并且可能有重复（两个object都指向同一个object），那么就需要在遍历时cache这一指针的结果。（因为我们无法确定当前指向的object已经被复制过与否，要避免出现重复复制的情况）

e.g.1 LeetCode: Copy List With Random Pointer

def copyRandomList(self, head: 'Node') -> 'Node':
    randoms: Dict[Optional['Node'], Optional['Node']] = {}


    old_dummy, new_dummy = Node(0), Node(0)
    old_dummy.next, new_dummy.next = head, None
    old_prev, new_prev = old_dummy, new_dummy

    # copy the list except random pointers
    while old_prev.next:
        new_prev.next = Node(old_prev.next.val)
        old_prev = old_prev.next
        new_prev = new_prev.next
        randoms[old_prev] = new_prev
    
    old_node, new_node = old_dummy.next, new_dummy.next
    
    # all nodes created, just need random pointers filled
    while old_node:
        new_node.random = randoms[old_node.random] if old_node.random else None
        old_node = old_node.next
        new_node = new_node.next
    
    return new_dummy.next

e.g.2 LeetCode: Clone Graph

如果遍历的顺序是可逆的（比如图），那么必须保证在访问任何一个其他节点之前就记录当前节点的copy，否则在分支路径能回到当前节点时会导致infinite的loop或者recursion。这与图的遍历用visited table是一致的。

def cloneGraph(self, node: 'Node') -> 'Node':
    self.oldToNew: Dict['Node', 'Node'] = {}

    if node is None: return None
    if node in self.oldToNew: return self.oldToNew[node]

    new_node = Node(node.val)
    # store in hash before recursion as graph might circle back to this node
    self.oldToNew[node] = new_node 
    new_node.neighbors = [self.cloneGraph(n) for n in node.neighbors]
    return new_node