138. 复制带随机指针的链表

138. 复制带随机指针的链表

题目描述如上,先是没看懂题,看了样例,就是将输入的链表再输出,但是每个节点有random指针,由于不能确定节点的random所指的节点是否已知;

1.遍历链表里的节点,并存在hashmap中
2.再遍历一遍,调整map中节点的next、random指针
3.返回map
/*
// 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 == NULL) return NULL;
        Node *tmp = head;
        unordered_map<Node*, Node*>mp;
        while(tmp!=NULL){
            mp[tmp] = new Node(tmp->val);
            tmp = tmp->next;
        }
        tmp = head;
        while(tmp!=NULL){
            mp[tmp]->next = mp[tmp->next];
            mp[tmp]->random = mp[tmp->random];
            tmp = tmp->next;
        }
        return mp[head];
    }
};

 

上一篇:​LeetCode刷题实战138:复制带随机指针的链表


下一篇:LeetCode 138 复制带随机指针的链表