Leetcode—138. 随机链表的复制【中等】（cend函数）

2024每日刷题（129）

Leetcode—138. 随机链表的复制

在这里插入图片描述

实现代码

/*
// 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:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) {
            return nullptr;
        }
        unordered_map<Node*, Node*> map;

        Node* cur = head;
        while(cur != nullptr) {
            Node* s = new Node(cur->val);
            map[cur] = s;
            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];
    }
};

运行结果

在这里插入图片描述

递归实现

/*
// 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:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) {
            return nullptr;
        }
        if(const auto it = map.find(head); it != map.cend()) {
            return it->second;
        }
        Node* newNode = new Node(head->val);
        map[head] = newNode;
        newNode->random = copyRandomList(head->random);
        newNode->next = copyRandomList(head->next);
        return newNode;
    }
private:
    unordered_map<Node*, Node*> map;
};