剑指 Offer 35 复杂链表的复制

概述

https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/

https://leetcode.com/problems/copy-list-with-random-pointer/

解法

核心就是：c2->random = idx2newNode[node2idx[idx2rand[idx]]];

即，

1. 由当前索引找出原本的链表中当前索引对应的原本的指针，
2. 由原本的指针找到索引，
3. 再由索引找到现在的指针。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, int> node2idx;
        unordered_map<int, Node*> idx2rand;
        unordered_map<int, Node*> idx2newNode;
        auto dummyHead = new Node(0);
        auto c = head;
        auto c2 = dummyHead;
        int idx = 0;
        while (c) {
            node2idx[c] = idx;
            idx2rand[idx] = c->random;
            c2->next = new Node(c->val);
            idx2newNode[idx] = c2->next;
            c = c->next;
            c2 = c2->next;
            idx ++;
        }
        c2 = dummyHead->next;
        idx = 0;
        while (c2) {
            if (idx2rand[idx] == nullptr) {
                c2->random = nullptr;
            } else {
                c2->random = idx2newNode[node2idx[idx2rand[idx]]];
            }
            c2 = c2->next;
            idx ++;
        }
        return dummyHead->next;
    }
};

Links: sword-offer-35

未经允许，禁止转载，本文源站链接：https://iamazing.cn/