[LeetCode] 138. Copy List with Random Pointer

1.原題リンク:https://leetcode.com/problems/copy-list-with-random-pointer/
2.問題の解き方
2.1マッピングテーブル

は、複製randomポインタ

を解決するために、新旧ノード間のマッピングテーブル:old->newを確立する.
2.2チェーンテーブルのクローン作成

新しいノードを含むクローンチェーンテーブルを作成します.A-->A'-->B-->B'-->C-->C'-->D-->D'

キー:A'のrandomポインタがAのrandomポインタが指すノードのnextノード

に等しい
3.アルゴリズム
3.1マッピング表

新旧ノード間のマッピングテーブルを確立する:old->new

チェーンテーブルを2回繰り返します.

最初の遍歴:新しいチェーンテーブルを構築し、新しいチェーンテーブルのnextポインタに値を付与するだけで、古いノードと新しいノードの間のマッピングテーブルを確立し、randomポインタに値を付与しない

第2パス:マッピングテーブルのマッピング関係に基づいて、新しいチェーンテーブルのrandomポインタに

を割り当てる.

3.2チェーンテーブルのクローン作成

最初のステップ:元のチェーンテーブルを巡回:A-->B-->C-->D、新しいノードを含むクローンチェーンテーブルを作成します:A-->A'-->B-->B'-->C-->C'-->D-->D'、randomポインタに

を割り当てないことに注意してください.

第2のステップ:新しいチェーンテーブルを巡回し、元のチェーンテーブルノードを巡回すると、そのノードの次のノード(すなわちAとA′の関係)のrandomポインタに値を付与し、このrandomポインタは元のノードのrandomポインタが指す次のノード

を指す.

第3歩:新しいチェーンテーブルを巡り、新しいノードを新しいチェーンテーブルから選択し、最終的なcopyチェーンテーブルを構成し、

に戻る.
4.実現

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

   
class Solution {
public:
    Node* copyRandomList(Node* head) {
        //            ：old->new
        map table;
        //     ：     ，    random      
        Node dummy(-1);
        Node *cur = head;
        Node *new_cur = &dummy;
        for(; cur != NULL; cur = cur->next, new_cur = new_cur->next){
            int v = cur->val;
            Node *new_node = new Node(v);
            table[cur] = new_node; //   ：                
            new_cur->next = new_node;
        }
        
        //     ：     random      
        cur = head;
        new_cur = dummy.next;
        for(; cur != NULL; cur = cur->next, new_cur = new_cur->next){
            Node *r = cur->random;
            Node *new_r = table[r];
            new_cur->random = new_r;
        }
        return dummy.next;
    }
};

    
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head)   return head;
        //copy new node and changing new node next pointer to old node next pointer and  old node next pointer to new node
        Node *newHead = NULL, *l1, *l2;
        for(l1 = head; l1 != NULL; l1 = l1->next->next){
            l2 = new Node(l1->val, l1->next, NULL);
            l1->next = l2;
        }
        newHead = head->next;
        //fixing the random pointer of the cloned list
        for(l1= head; l1 != NULL; l1 = l1->next->next){
            if(l1->random) l1->next->random = l1->random->next;
        }
        //changing the next node of both old and new list
        for(l1 = head; l1 != NULL; l1 = l1->next){
            l2 = l1->next;
            l1->next = l2->next;
            if(l2->next)l2->next = l2->next->next;
        }
        return newHead;
    }
};