复杂链表的复制
    题目链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/
    图片.png
    思路：比较直接的想法是按序遍历原链表，用hashmap与新链表的每个节点建立一一对应的关系，然后再遍历新链表并根据对应关系补充random指针。

    • 注意在下面的代码中并未特别处理random = NULL的情形，原因是在C++的unordered_map中，如果对不存在的key调用了[]运算符，会直接在原map中insert该key，并用默认构造函数构造其value；故调用m[NULL]将会把它的值赋为NULL，恰好符合要求
      • 从代码健壮性和可读性上来说应该显式处理该情况
        1. class Solution {
        2. public:
        3. Node* copyRandomList(Node* head) {
        4.    if (!head) {
        5.        return NULL;
        6.    }
        7.    unordered_map<Node*, Node*> m;
        8.    Node* curr = head;
        9.    while (curr) {
        10.        m[curr] = new Node(curr->val);
        11.        curr = curr->next;
        12.    }
        13.    curr = head;
        14.    while (curr) {
        15.        m[curr]->next = m[curr->next];
        16.        m[curr]->random = m[curr->random];
        17.        curr = curr->next;
        18.    }
        19.    return m[head];
        20. }
        21. };
        上面的思路需要用O(N)的额外空间，看题解有一种巧妙的不使用额外空间的解法：先将原链表与新链表交错拼接，然后构建新链表节点的random节点，再将两个链表拆分：
        图片.png
        参考代码：
        1. class Solution {
        2. public:
        3. Node* copyRandomList(Node* head) {
        4.    if(head == nullptr) return nullptr;
        5.    Node* cur = head;
        6.    // 1. 复制各节点，并构建拼接链表
        7.    while(cur != nullptr) {
        8.        Node* tmp = new Node(cur->val);
        9.        tmp->next = cur->next;
        10.        cur->next = tmp;
        11.        cur = tmp->next;
        12.    }
        13.    // 2. 构建各新节点的 random 指向
        14.    cur = head;
        15.    while(cur != nullptr) {
        16.        if(cur->random != nullptr)
        17.            cur->next->random = cur->random->next;
        18.        cur = cur->next->next;
        19.    }
        20.    // 3. 拆分两链表
        21.    cur = head->next;
        22.    Node* pre = head, *res = head->next;
        23.    while(cur->next != nullptr) {
        24.        pre->next = pre->next->next;
        25.        cur->next = cur->next->next;
        26.        pre = pre->next;
        27.        cur = cur->next;
        28.    }
        29.    pre->next = nullptr; // 单独处理原链表尾节点
        30.    return res;      // 返回新链表头节点
        31. }