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

力扣

解法一

/*
// 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 == nullptr) {
            return head;
        }
 
        Node *p = head;
        while (p != nullptr) {
            Node *newNode = new Node(p->val);
            newNode->next = p->next;
            p->next = newNode;
            p = newNode->next;
        }      
 
        p = head;
        while (p != nullptr) {
            if (p->random != nullptr) {
                p->next->random = p->random->next;
            }
            p = p->next->next;
        }
 
        Node *dummy = new Node(-1);
        dummy->next = head;
        Node *curr = dummy;
        p = head;
        while (p != nullptr) {
            curr->next = p->next;
            curr = curr->next;
            p->next = curr->next;
            p = p->next;
        }
 
        return dummy->next;
    }
};

解法二

/*
// 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 == nullptr) {
            return head;
        }
 
        unordered_map map;
        Node *p = head;
        while (p != nullptr) {
            Node *newNode = new Node(p->val);
            map[p] = newNode;
            p = p->next;
        }
 
        p = head;
 
        while (p != nullptr) {
            Node *newNode = map[p];
            if (p->next != nullptr) {
                newNode->next = map[p->next];
            }
            if (p->random != nullptr) {
                newNode->random = map[p->random];
            }
            p = p->next;
        }
 
        return map[head];        
    }
};