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.

tricky solution

/**
 * 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 *p = head, *p2;
        while ( p != NULL ) {
            RandomListNode *copyNode = new RandomListNode(p->label);
            RandomListNode *next = p->next;
            p->next = copyNode;
            copyNode->next = next;
            p = next;
        }
        p = head;
        p2 = head->next;
        while ( true ) {
            // 1st note
            if ( p->random != NULL ) p2->random = p->random->next;
            p = p2->next;
            if ( p == NULL ) break;
            p2 = p->next;
        }
        p = head;
        p2 = head->next;
        RandomListNode *newHead = head->next;
        while ( true ) {
            RandomListNode *next = p2->next;
            if ( next == NULL ) {
                // 2nd node
                p->next = NULL;
                break;
            }
            RandomListNode *next2 = next->next;
            p->next = next;
            p2->next = next2;
            p = next;
            p2 = next2;
        }
        return newHead;
    }
};

Notes
容易出错的地方：

1. 一个node的random可能是NULL!
2. 注意维护原linked list node的连接，尤其是最后一个NULL的地方。(make it point to NULL before break!）

naive but straight forward solution

/**
 * 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) {
        unordered_map<RandomListNode*, RandomListNode*> map;
        RandomListNode *p = head;
        if ( head == NULL ) return NULL;
        while ( p != NULL ) {
            RandomListNode* p_copy = new RandomListNode(p->label);
            map[p] = p_copy;
            p = p->next;
        }
        p = head;
        while ( p != NULL ) {
            if ( p->next != NULL ) map[p]->next = map[p->next];
            if ( p->random != NULL) map[p]->random = map[p->random];
            p = p->next;
        }
        return map[head];
    }
};

Notes

1. 不要忘记把node连起来。。。
2. 注意random或者next为NULL的情况