Hard-テーマ20:138.Copy List with Random Pointer

タイトル原文:A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list. 深さは1つのチェーンテーブルをコピーして、このチェーンテーブルは普通の単鎖テーブルの基礎の上で1つのrandomポインタを増加して、チェーンテーブルのいかなる1つのノードを指すことができて、だからランダムなチェーンテーブルと呼ばれます.テーマ分析:元のチェーンテーブルを2回遍歴するには、randomノードを持たずに元のチェーンテーブルをコピーし、ハッシュテーブルで元のチェーンテーブルと新しいチェーンテーブルのマッピング関係を確立します.元のチェーンテーブルのi番目のノードはkeyで、新しいチェーンテーブルのi番目のノードはvalueです(なぜ逆さまにできないのか考えてみてください).2回目のスキャン時にrandomノードをコピーし、元のチェーンテーブルと新しいチェーンテーブルを同時に最初からスキャンし、新しいチェーンテーブルの現在のノードのrandom値を元のチェーンテーブルrandomのハッシュテーブルでのマッピングに等しくします.総複雑度O(n).ソース:(language:cpp)

class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        map<RandomListNode *,RandomListNode *> m;
        m[NULL]=NULL;
        RandomListNode *t=new RandomListNode(0);
        RandomListNode *p1=head,*p2=t;

        while(p1)
        {
            p2->next=new RandomListNode(p1->label);
            m[p1]=p2->next;
            p1=p1->next;
            p2=p2->next;
        }
        p1=head;
        p2=t->next;
        while(p1)
        {
            p2->random=m[p1->random];
            p1=p1->next;
            p2=p2->next;    
        }
        p2=t->next;
        return p2;
    }
};

成績:128 ms,beats 19.31%,衆数108 ms,19.45%Cmershenの砕けた考え:最初はハッシュテーブルでチェーンテーブルの各ノードを[1,length]にマッピングし,次にrandomを持たないものを複製し,2回目は並列に2つのチェーンテーブルを掃き,元のrandomが指す「下付き」を得て,新しいチェーンテーブルの中で最初から探し始めた.しかし,このような時間的複雑さはO(n 2)であり,望ましくない.