复制复杂链表

Deep Copy a complicated linked list

哈希表+递归实现最为简洁，可以统一copy的两种情况。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    unordered_map<Node*, Node*> m;
    Node* copyRandomList(Node* head) {
        if (head == nullptr) return nullptr;
        if (m.count(head)) return m[head];
        else {
            Node* tmp = new Node(head->val);
            m[head] = tmp;
            tmp->next = copyRandomList(head->next);
            tmp->random = copyRandomList(head->random);
            return tmp;
        }
    }
};

遍历两边不太聪明的样子：

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == NULL) return NULL;
        Node *head2 = new Node(head->val);
        Node *cur = head, *cur2 = head2;
        // first round
        map<Node*, Node*> m;
        m[NULL] = NULL;
        m[cur] = cur2;
        while (cur->next) {
            cur = cur->next;
            Node *tmp = new Node(cur->val);
            cur2->next = tmp;
            cur2 = tmp;
            m[cur] = cur2;
        }
        // second round
        cur = head; cur2 = head2;
        cur2->random = m[cur->random];
        while (cur->next) {
            cur = cur->next;
            cur2 = cur2->next;
            cur2->random = m[cur->random];
        }
        return head2;
    }
};

脑内宇宙大爆炸的空间优化做法：

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) {
            return nullptr;
        }
        for (Node* node = head; node != nullptr; node = node->next->next) {
            Node* nodeNew = new Node(node->val);
            nodeNew->next = node->next;
            node->next = nodeNew;
        }
        for (Node* node = head; node != nullptr; node = node->next->next) {
            Node* nodeNew = node->next;
            nodeNew->random = (node->random != nullptr) ? node->random->next : nullptr;
        }
        Node* headNew = head->next;
        for (Node* node = head; node != nullptr; node = node->next) {
            Node* nodeNew = node->next;
            node->next = node->next->next;
            nodeNew->next = (nodeNew->next != nullptr) ? nodeNew->next->next : nullptr;
        }
        return headNew;
    }
};