leetcode hot100-32 随机链表的复制

方法一： 拼接 + 拆分 空间复杂度O(1)

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr)
            return nullptr;
        // 1.复制每个节点，把新节点直接插入到原节点后面
        Node* cur = head;
        while (cur != nullptr) {
            Node* node = new Node(cur->val);
            node->next = cur->next;
            cur->next = node;
            cur = node->next;
        }
        // 2.复制 random 指针，每个要复制的 random 是 cur->random 的下一个节点
        cur = head;
        while (cur != nullptr) {
            if (cur->random != nullptr)
                cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        // 3.拆分链表
        Node* newhead = head->next;
        Node* p = newhead;
        cur = head;
        while (cur != nullptr) { //若cur存在，则p一定存在
            cur->next = cur->next->next; // 还原原链表
            if (p->next != nullptr)//若p->next存在，则cur->next一定存在
                p->next = p->next->next; // 还原新链表
            cur = cur->next;
            p = p->next;
        }
        return newhead;
    }
};

方法二：哈希表 空间复杂度O(N)

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head ==nullptr) return nullptr;
        Node* cur = head;
        unordered_map<Node*,Node*> map;
        while(cur != nullptr) {
            map[cur] = new Node(cur->val);
            cur = cur->next; 
        } 
        cur = head;
        while(cur!=nullptr) {
            map[cur]->next = map[cur->next];
            map[cur]->random = map[cur->random];
            cur = cur->next;
        }
        return map[head];
    }
};