JZ25 复杂链表的复制

• 题目描述
• 思路分析
• 代码实现

题目描述

点这里

思路分析

链表模拟+哈希表
没有的节点hash创建出来。

代码实现

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* head) {
        unordered_map<RandomListNode*, RandomListNode*> hash;
        hash[nullptr] = nullptr;
        auto dummy = new RandomListNode(-1), tail = dummy;

        while(head)
        {
            if(!hash.count(head)) hash[head] = new RandomListNode(head->label);
            if(!hash.count(head->random)) hash[head->random] = new RandomListNode(head->random->label);

            tail->next = hash[head];
            tail->next->random = hash[head->random];

            tail = tail->next;
            head = head->next;
        }

        return dummy->next;
    }
};