LeetCode1024 -- 贪心

1. 题目描述

这题题意感觉说的不是很清楚，容易让人产生歧义！其实题意很简单，给你一个链表 head，你深拷贝它，然后返回即可，注意不能修改原链表

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

2. 坑

首先，这题绝对没你看上去的那么简单，复制链表？太简单了，不就是链表的创建吗？
不！本题有一个有意思的地方，就是它有一个随机指针，随机指针以为着什么？
意味着，它指向的节点，可能还未创建！
因此说，我们不能直接遍历链表，来创建新链表，需要一些特殊方法

3. 思路1 -- 哈希表

\(O(N)\)时间， \(O(N)\)空间

思路呢，也很简单，既然随机指针可能指向一个还未创建的节点，那么我们就先创建它，然后通过哈希表存起来，并与原链表的相应节点做映射。
这样，当我们下次遍历到这个随机节点时，我们可以检查一下哈希表，看看是否已经建立过了，避免重复创建节点。

代码

// 本题的难点主要在于，当我们需要将指针指向某个节点时
// 随机指针指向的节点可能还不存在
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        Node *dummy = new Node(-1);
        Node *cur = dummy;
        // refto 存储的时，原链表head与它的拷贝之间的映射
        unordered_map<Node*, Node*> refto;
        while(head) { 
            // 遍历原链表的每一个节点，创建它自己和他的random指针指向的节点
            // 并让它的random指针指向原链表random指针指向的节点
            if(refto[head] == nullptr) {
                Node *newNode = new Node(head->val);
                refto[head] = newNode;
            }
            if(head->random && refto[head->random] == nullptr) {
                Node *newNode = new Node(head->random->val);
                refto[head->random] = newNode;
            }
            
            refto[head]->random = refto[head->random];
            cur->next = refto[head];
            cur = refto[head];

            head = head->next;
        }
        return dummy->next;
    }
};

4. 思路2 -- 原地修改

\(O(N)\) 时间， \(O(1)\)空间。
注意在计算空间复杂度时，是不考虑创建新链表产生的空间的，因为那是必须的，我们主要考虑的时额外空间的复杂度。