Copy List with Random Pointer

Copy List with Random Pointer – leetcode
描述：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.
解法：
第一步应该是将链表中的每一个结点拷贝一份，并插入到该结点的后面，重新构建成一个新的链表（此时，仅仅拷贝了链表的值，对所以拷贝结点的random都设为空）
如图：

第二步：根据构建后的新链表，在copyNode结点上恢复原链表对应结点的random指针
例如图：

第三步，将原链表和copy出来的链表断开，恢复原链表，构建新拷贝出来的链表，返回即可。

class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if (head == NULL) return NULL;
        //第一步：链接新表
        RandomListNode *curList = head; //旧链表
        RandomListNode *oldNext = NULL; //旧链表的下一个
        RandomListNode *copyOld = NULL; //复制旧链表的一个值

        while (curList != NULL){
            oldNext = curList -> next;
            copyOld = new RandomListNode(curList -> label);
            //将copyOld 链接到旧链表上
            copyOld -> next = curList -> next;
            curList -> next = copyOld;
            curList = oldNext;
        }
        //第二步：确定新表的random指针
        curList = head;
        while (curList != NULL){
            curList -> next -> random = (curList -> random == NULL) ? NULL : curList -> random -> next;
            curList = curList -> next -> next;
        }

        //第三步：恢复旧链表，链接新链表
        curList = head;
        RandomListNode *newList = head -> next;//将copy出来的链表链接成一个新链表，并且恢复旧链表
        while(curList != NULL){
            oldNext = curList -> next -> next;
            copyOld = curList -> next;
            curList -> next = oldNext;
            copyOld -> next = (oldNext == NULL)?NULL:oldNext->next;
            curList = oldNext;
        }
        return newList;
    }
};