[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.

Analysis:

基本思想：拷贝每个node，使得1->2->3变成1->1->2->2->3->3.然后fix random pointer，因为每个拷贝的node的random都是原来node的下一个，除非是NULL。最后从list中分离拷贝node

/**
 * 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 head;
        //duplicate node
        RandomListNode* curr = head;
        while(curr != NULL)
        {
            RandomListNode* next = curr->next;
            RandomListNode* newNode = new RandomListNode(curr->label);
            curr->next = newNode;
            newNode->next = next;
            curr = next;
        }
        
        //copy random
        curr = head;
        while(curr != NULL)
        {
            if (curr->random != NULL)
                curr->next->random = curr->random->next;
            curr = curr->next->next;
        }
        
        //split the list
        RandomListNode* newHead = NULL;
        RandomListNode* p = NULL;
        curr = head;
        while(curr != NULL)
        {
            if (p == NULL)
            {
                newHead = curr->next;
                p = curr->next;
            }
            else
            {
                p->next = curr->next;
                p = p->next;
            }
            curr->next = curr->next->next;
            curr = curr->next;
        }
        
        return newHead;
        
    }
};