Leetcode 138. 复制带随机指针的链表（DAY 148) ---- LeetCode 精选 TOP 面试题（内含闲聊）

缺乏、安全感 2022-09-06 10:15 108阅读 0赞

### 文章目录 ###

*   *  闲聊
     *  原题题目
     *  代码实现（首刷自解 C++）

--------------------

## 闲聊 ##

--------------------

**这里也闲聊不到什么 hhh 可能有的hxd就会好奇 上一次发题的时候 明明是DAY 143 怎么这里就变成DAY 148了呢 中间那么多天被我吞了吗 哈哈 那肯定不是这样子的啊 因为现在在补《LeetCode 精选 TOP 面试题》这个题集里面的题 里面现在做的部分很多都是原来做过的题 做过的题我就直接二次编辑到原来写过的博客里面去了 就没有再单独发出来了 … 整整隔了差不多4-5天今天才写到新题 哈哈 就这样子哈**

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70]

--------------------

## 代码实现（首刷自解 C++） ##

--------------------

/* // 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)   return head;
            unordered_map<Node*,int> map;
            vector<Node*> v;
            Node* ptr = head;
            int cnt = 0;
            while(ptr)
            { 
                map[ptr] = cnt++;
                v.emplace_back(new Node(ptr->val));
                ptr = ptr->next;
            }
            map[ptr] = cnt;
            v.emplace_back(nullptr);
    
            ptr = head;
            while(ptr)
            { 
                v[map[ptr]]->random = v[map[ptr->random]];
                v[map[ptr]]->next   = v[map[ptr->next]];
                ptr = ptr->next;
            }
    
            return v[0];
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70]: /images/20220829/8d5092ee6c5c4c96b9445ec97f98aaa2.png