LeetCode_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.
チェーンテーブルの基本操作.
考え方:randomポインタがあるので、すべてのノードをコピーしてから、ランダムなポインタを変更することができます.
私の最も出た方法(コードの注釈部分)は、ランダムポインタのコピーに対して、毎回チェーンテーブルを巡回してポインタの位置を決定し、アルゴリズムの時間が複雑にO(n 2)になり、最後にコミットがタイムアウトします.
Discussでは、同じようにチェーンテーブルの基本的なレプリケーションを最初に完了する牛人のやり方が見られますが、レプリケーション時に新しくレプリケーションされたノードを元のノードの後継として格納することで、新しくレプリケーションされたノードのrandomポインタがソースノードrandomのnextとして容易に位置決めされます.少し回りくどいことを言って、コードを見て何でも分かりました.

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    //RandomListNode *copyRandomList(RandomListNode *head) {
    //    if (head==NULL)
    //    {
    //        return NULL;
    //    }
    //    
    //    RandomListNode *pCurrent=head->next;
    //    RandomListNode *copyhead=new RandomListNode(head->label);
    //    RandomListNode *pCurrentCopy=copyhead;
    //    //     next   
    //    while (pCurrent!=NULL)
    //    {
    //        pCurrentCopy->next=new RandomListNode(pCurrent->label);
    //        pCurrent=pCurrent->next;
    //        pCurrentCopy=pCurrentCopy->next;
    //    }

    //    //     random  
    //    pCurrent=head;
    //    pCurrentCopy=copyhead;
    //    while (pCurrent!=NULL)
    //    {
    //        RandomListNode *pRandom=pCurrent->random;
    //        if (pRandom!=NULL)
    //        {
    //            RandomListNode *ptemp=head;
    //            RandomListNode *pCopyTemp=copyhead;
    //            while (ptemp!=pRandom)
    //            {
    //                ptemp=ptemp->next;
    //                pCopyTemp=pCopyTemp->next;
    //            }
    //            pCurrentCopy->random=pCopyTemp;
    //        }
    //        pCurrent=pCurrent->next;
    //        pCurrentCopy=pCurrentCopy->next;
    //    }
    //    return copyhead;
    //}
    RandomListNode *copyRandomList(RandomListNode *head) {
        if(head == NULL) return NULL;
        RandomListNode *p = head;
        do {
            RandomListNode *q = p->next;
            p->next = new RandomListNode(p->label);
            p->next->next = q;
            p = q;
        } while(p != NULL);
        p = head;
        do {
            p->next->random = (p->random == NULL) ? NULL : p->random->next;
            p = p->next->next;
        } while(p != NULL);
        p = head;
        RandomListNode *r = head->next;
        for(RandomListNode *q = r;;) {
            p->next = q->next;
            p = p->next;
            if(p == NULL) break;
            q->next = p->next;
            q = q->next;
        }
        return r;
    }
};