【题目/链表训练】链表

一、随机链表的复制

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*, Node*> NodeMap;
        Node* copyhead = nullptr, * copytail = nullptr;
        Node* cur = head;
        while (cur)  //遍历原链表
        { //深拷贝
            if (copytail == nullptr)
            {
                copyhead = copytail = new Node(cur->val);
            }
            else
            {
                copytail->next = new Node(cur->val);
                copytail = copytail->next;
            }
            //原节点和拷贝节点map kv存储，建立映射关系
            NodeMap[cur] = copytail;
            cur = cur->next;
        }


        //处理random
        cur = head;
        Node* copy = copyhead;
        while (cur)
        {
            if (cur->random == nullptr)
            {
                copy->random = nullptr;
            }
            else
            {
                copy->random = NodeMap[cur->random];
            }
            cur = cur->next;
            copy = copy->next;
        }
        return copyhead;
    }
};