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.

S1: hashmap存储旧pointer和新node的对应关系

因为指向同一node的pointer的值是一样的，不管是*random, *next,还是*head，只要有pointer的值就能通过hashmap找到对应得node

    RandomListNode *copyRandomList(RandomListNode *head) {
        unordered_map<RandomListNode*, RandomListNode*> map;
        for(RandomListNode *p = head; p; p = p->next) map[p] = new RandomListNode(p->label);
        for(RandomListNode *p = head; p; p = p->next){
            RandomListNode *node = map[p];
            if(p->next) node->next = map[p->next];
            if(p->random) node->random = map[p->random];
        }
        return map[head];
    }

S2: 利用*next重新构建链表

考虑到我们要找到*random对应的新node,可以将旧node中的pointer指向它对应的新newnode。同时要保证旧node的next能变回原样，可以将newnode的\next指向旧node在旧链表中的原next node。

空间复杂度为O(1)，但是需要在过程中改变原链表指针线程安全性不好。

    RandomListNode *copyRandomList(RandomListNode *head) {
        if(!head) return NULL; 
        //reconstruct list, using next pointer
        for(RandomListNode *p = head; p; p = p->next->next) {
            RandomListNode *node = new RandomListNode(p->label);
            node->next = p->next;
            p->next = node;
        }
        RandomListNode *new_head = head->next;
        //assign random pointer
        for(RandomListNode *p = head; p; p = p->next->next) {
            if(p->random) p->next->random = p->random->next;
        }
        //recover original list and new list
        for(RandomListNode *p = head; p; p = p->next) {
            RandomListNode *node = p->next;
            p->next = node->next;
            node->next = node->next? node->next->next: NULL;
        }
        return new_head;
    }