跳转至

138.复制带随机指针的链表 (Medium)*

题目描述*

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的 深拷贝。 

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

  • val：一个表示 Node.val 的整数。
  • random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。

提示*

-10000 <= Node.val <= 10000

Node.random 为空（null）或指向链表中的节点。

节点数目不超过 1000 。

代码*

带随机指针的链表深拷贝主要的问题就是在设置 random 指针时指向的结点可能还未创建。因此想到把链表项复制后存入哈希表，然后再设置 next 和 random 指针。这需要两次遍历，可以优化为一次遍历，即如果 random 对应的结点尚未复制，则复制存入哈希表；已复制则直接设置。

另有一种做法就是先把链表复制，新生成的结点在原结点后，然后分离出来，leetcode 上看到有人称之为 有丝分裂，感觉挺形象。此方法使用原链表的 next 域保存新结点，那么我们同样可以用 random 域保存新结点，然后再分离。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node *p = head;
        Node *tail = new Node(-1);
        unordered_map<Node*, Node*> saveMap;
        Node *tmp;
        int cnt = 0;
        while(p != nullptr) {
            if(saveMap.find(p) == saveMap.end()) {
                tmp = new Node(p->val);
                saveMap[p] = tmp;
            }
            Node *copied = saveMap[p];
            if(p->random != nullptr) {
                if(saveMap.find(p->random) == saveMap.end()) {
                    tmp = new Node(p->random->val);
                    saveMap[p->random] = tmp;
                    copied->random = tmp;
                }else {
                    copied->random = saveMap[p->random];
                }
            }
            tail->next = copied;
            tail = tail->next;
            p = p->next;
            cnt++;
        }
        return saveMap[head];
    }
};

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) {
            return nullptr;
        }
        Node *cur = head, *copied = nullptr;
        // copy 所有结点直接放到原结点后
        while(cur != nullptr) {
            copied = new Node(cur->val);
            copied->next = cur->next;
            cur->next = copied;
            cur = cur->next->next;
        }
        // 设置 random 指针
        cur = head;
        while(cur != nullptr) {
            if(cur->random != nullptr) {
                cur->next->random = cur->random->next;
            }
            cur = cur->next->next;
        }
        // 分离复制链表
        cur = head;
        Node *res = cur->next;
        while(cur != nullptr) {
            copied = cur->next;
            cur->next = copied->next;
            if(copied->next != nullptr) {
                copied->next = copied->next->next;
            }
            cur = cur->next;
        }
        return res;
    }
};

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) {
            return nullptr;
        }
        // 与上一种类似，只是换成了 random 
        Node *cur = head, *copied = nullptr;
        while(cur != nullptr) {
            copied = new Node(cur->val);
            copied->next = cur->random;
            cur->random = copied;
            cur = cur->next;
        }
        cur = head;
        while(cur != nullptr) {
            copied = cur->random;
            copied->random = (copied->next == nullptr) ? nullptr : copied->next->random;
            cur = cur->next;
        }
        cur = head;
        Node *res = cur->random;
        while(cur != nullptr) {
            copied = cur->random;
            cur->random = copied->next;
            copied->next = (cur->next == nullptr) ? nullptr : cur->next->random;
            cur = cur->next;
        }
        return res;
    }
};
最后更新: July 23, 2022