105. Copy List with Random Pointer

不用hash map节省 space！！！

Code(Language:C++) (Judger:ip-172-31-12-4)

/**
 * 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:
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    RandomListNode *copyRandomList(RandomListNode *head) {
        // write your code here
        RandomListNode *copy = head; 
        if(head == NULL){
            return head; 
        }
        // add new node
        while(copy != NULL){
            RandomListNode *tmp = copy->next; 
            copy->next = new RandomListNode(copy->label); 
            copy->next->next = tmp; 
            copy = tmp; 
        }
        copy = head; 
        // add random pointer
        while(copy != NULL && copy->next != NULL){
            if(copy->random){
               copy->next->random = copy->random->next;
            }
            copy = copy->next->next; 
        }
        // break the link between old and new 
        RandomListNode *newHead = head->next;
        copy = newHead; 
        while(copy != NULL && copy->next != NULL){
            copy->next = copy->next->next; 
            copy = copy->next; 
        }
        return newHead; 
    }
};