leetcode-链表深度拷贝

点击：题目链接：请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

思路

链表拷贝有两种，浅层拷贝和深度拷贝。
浅层拷贝—拷贝后的链表和之前的共享同一内存，即仍指向同一份next链表
深度拷贝—重新申请内存来放置拷贝后的链表

故我们可以直接使用一个map表一一保存每个结点，再进行拷贝复制每个结点的关系。

代码

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) {
        Node* cur = new Node(0);
        cur = head;
        unordered_map<Node*, Node*> hash;
        while(cur != nullptr){          //将每个结点一一对应存入哈希表
            hash[cur] = new Node(cur->val);
            cur = cur->next;
        }
        cur = head;

        while(cur != nullptr){           //拷贝每个节点的对应关系
            hash[cur]->next = hash[cur->next];
            hash[cur]->random = hash[cur->random];
            cur = cur->next;
        }
        return hash[head];
    }
};

小总结

读题的时候一定要确切的明白题意。比如这道，刚读完，我一直以为要自己来决定结点之间的随即关系（浪费了比较长的时间后感觉不对劲）。结果只需要复制原来的。