剑指 Offer 35 复杂链表的复制

Tag: 剑指-Offer Posted on 2022-02-25 23:06:58 Edited on 2022-02-25 23:55:41 Views: 299

概述

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;
    }
};

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