35. 复杂链表的复制.md

解题思路

1. 使用 map 存储节点间映射

借助 map 完成映射 map 中存储 原节点:新节点，原节点作为 key，新节点作为 value 第一次遍历时，建立映射 第二次遍历时，根据 map 重建映射

func copyRandomList(head *Node) *Node {
    m := make(map[*Node]*Node)
    cur := head
    // 第一次遍历，建立 原节点到新节点的映射
    for cur != nil {
        m[cur] = &Node{Val:cur.Val}
        cur = cur.Next
    }
    cur = head
    // 第二次遍历，根据 map 重建映射
    for cur != nil {
        // `m[cur].Next`是新节点的Next，`m[cur.Next]`原节点的 Next 对应的新节点
        m[cur].Next = m[cur.Next]
        m[cur].Random = m[cur.Random]
        cur = cur.Next
    }
    return m[head]
}