LeetCode: Copy List with Random Pointer [138]

/**
 * 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) {
        map<RandomListNode*, RandomListNode*> old2new;
		
		RandomListNode*newhead=NULL;
		RandomListNode*oldpointer=head;
		RandomListNode*newpointer=NULL;
		RandomListNode*prevnew=NULL;
		//生成新链表构造旧链表结点和新链表结点的对应关系
		while(oldpointer){
			newpointer=new RandomListNode(oldpointer->label);
			if(prevnew==NULL)newhead=newpointer;
			else{
				prevnew->next=newpointer;
			}
			prevnew=newpointer;
			
			old2new[oldpointer]=newpointer;
			oldpointer=oldpointer->next;
		}
		//更新random指针
		oldpointer=head;
		newpointer=newhead;
		while(oldpointer){
			newpointer->random=old2new[oldpointer->random];
			oldpointer=oldpointer->next;
			newpointer=newpointer->next;
		}
		return newhead;
    }
};