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.

题目很简单，就是单链表的深拷贝，但是每个节点随机指向其中一个节点。

所以在深拷贝的时候不能直接得到随机点，需要建立原链表与新链表的映射，我用了map，第二轮循环就可以查找设置了：

#include<iostream>
#include <set>
#include <string>
#include <vector>
#include <map>

using namespace std;


 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){
			return NULL;
		}
		
		RandomListNode * reshead = new RandomListNode(head->label);
		map<RandomListNode *, RandomListNode *> nodeMap1;

		RandomListNode * pre = reshead;
		RandomListNode * cur = pre->next;

		nodeMap1[head] = reshead;
		
		RandomListNode *srcNode = head->next;
		while (srcNode)
		{
			cur = new RandomListNode(srcNode->label);
			nodeMap1[srcNode] = cur;

			pre->next = cur;
			pre = cur;
			cur = cur->next;

			
			srcNode = srcNode->next;
		}
		srcNode = head;
		cur = reshead;
		while (srcNode)
		{
			cur->random = nodeMap1[srcNode->random];

			cur = cur->next;
			srcNode = srcNode->next;
		}

		return reshead;
    }

	void print(RandomListNode *head){
		while(head)
		{
			printf("val:%d", head->label);
			if (head->random){
				printf(" random:%d", head->random->label);
			}
			printf("\n");
			
			head = head->next;
		}
	}
};

int main(){
	RandomListNode* p1 = new RandomListNode(1);
	RandomListNode* p2 = new RandomListNode(2);
	RandomListNode* p3 = new RandomListNode(3);
	p1->next = p2;
	p2->next = p3;

	p1->random = p3;
	p2->random = p2;
	p3->random = p1;

	Solution s;
	s.print(s.copyRandomList(p1));
}

leetcode: Copy List with Random Pointer解法,布布扣,bubuko.com

leetcode: Copy List with Random Pointer解法

原文：http://blog.csdn.net/boyxiaolong/article/details/22729299