leetcode 138. Copy List with Random Pointer

138. Copy List with Random Pointer

分三步：1.在原有list每個節點的後面增加與原節點值相同的節點

　　　　2.在這些新生成的節點中增加随機節點

　　　　3.将原有的節點和新生成的節點進行分離

注意：

if(cur->random)

randNode = cur->random->next;

else

randNode = NULL;

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == NULL)
            return NULL;
        Node* cur = head;
        while(cur){
            Node* tmp = cur->next;
            Node* newNode = new Node(cur->val);
            cur->next = newNode;
            newNode->next = tmp;
            cur = tmp;
        }
        cur = head;
        while(cur){
            Node* tmp = cur->next;
            Node* randNode;
            if(cur->random)
                randNode = cur->random->next;
            else
                randNode = NULL;
            tmp->random = randNode;
            cur = cur->next->next;
        }
        cur = head;
        Node* res = head->next;
        Node* result = head->next;
        while(cur){
            cur->next = cur->next->next;
            if(res->next)
                res->next = res->next->next;
            else
                res->next = NULL;
            cur = cur->next;
            res = res->next;
        }
        return result;
    }
};