leecode 解题总结：138. Copy List with Random Pointer

#include <iostream>#include <stdio.h>#include <vector>#include <string>using namespace std;/*问题: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.分析：问题的难点在于那些随意指向的结点也是链表中的某个结点，但是如果拷贝的时候，你新建结点，你不知道任意结点后续指向哪个结点。必须要先根据next的指向，把标准链表建立起来，但是就算直接建立好，你不知道随意的结点指向是哪一个。难道直接将新生成的结点替换掉原有链表中的结点。还是用原链表的结点指向新链表的结点。可以将新生成每个结点插入到当前结点的后面比如对于链表:1->2->3原本要生成的链表是:T1->T2->T3现在将Ti插入到第i个结点后面，变成1->T1->2->T2->3->T3，假设结点p是原始链表中任意一个结点，我们只需要使得p->next->random=p->random->next，即可然后p=p->next->next即可拷贝完成后，然后将新的链表从复合链表中剥离出来p=head; p=p->next->nextNode* newP=p->next;nextNewP=p->next;然后newP->next=nextNewP;newP=nextNewP即可输入:5(结点元素个数)1 2 3 4 52 3 4 0 151 2 3 4 52 3 4 0 -1输出:1 2 3 4 5(链表正常遍历结果)3 4 5 1 2(链表随意结点遍历结果)1 2 3 4 53 4 5 1 NULL关键:1 在标准链表每一个结点之后插入新生成的结点，假设结点p是原始链表中任意一个结点，我们只需要使得p->next->random=p->random->next，即可然后p=p->next->next即可拷贝完成后，然后将新的链表从复合链表中剥离出来p=head; p=p->next->nextNode* newP=p->next;nextNewP=p->next;然后newP->next=nextNewP;newP=nextNewP*/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* node = head;		RandomListNode* nextNode = NULL;		//将每个新的结点插入到对应结点的后面		while(node)		{			RandomListNode* newNode = new RandomListNode(node->label);			nextNode = node->next;			node->next = newNode;			newNode->next = nextNode;			node = nextNode;		}		//建立好链表之后，接下来设置random结点指向:p->next->random = p->random->next		node = head;		while(node)		{			if(node->next)			{				if(node->random)				{					node->next->random = node->random->next;				}				else				{					node->next->random = NULL;				}				node = node->next->next;			}			else			{				break;			}		}		//设定好random结点指向，现在剥离链表		node = head;		RandomListNode* newNode = NULL;		RandomListNode* nextNewNode = NULL;		//需要找到尾结点，设置尾结点为NULL		RandomListNode* PRevious = NULL;		RandomListNode* newPrevious = NULL;		RandomListNode* newHead = NULL;		bool isFirst = true;		while(node)		{			newNode = node->next;			newPrevious = newNode;			if(isFirst)			{				newHead = newNode;				isFirst = false;			}			//让原链表当前直接点，指向newNode下一个结点，如果newNode为空，结束			if(newNode)			{				previous = node;				node->next = newNode->next;				node = newNode->next;			}			else			{				break;			}			if(node)			{				nextNewNode = node->next;				//设置结点指向				newNode->next= nextNewNode;				newNode = nextNewNode;			}			else			{				break;			}				}		previous->next = NULL;		newPrevious->next = NULL;		return newHead;    }};//第二个参数是随意指向的结点下标集合,如果出现-1，表示随意结点为NULLRandomListNode* buildList(vector<int>& nums , vector<int>& randomNodeIndexs){	if(nums.empty())	{		return NULL;	}	int size = nums.size();	RandomListNode* root = NULL;	RandomListNode* tail = NULL;	vector<RandomListNode*> nodes;	for(int i = 0 ; i < size ; i++)	{		if(i)		{			RandomListNode* node = new RandomListNode(nums.at(i));			nodes.push_back(node);			tail->next = node;			tail = node;		}		else		{			root = new RandomListNode(nums.at(i));			tail = root;			nodes.push_back(root);		}	}	//下面进行随意结点指向的构建	int value;	for(int i = 0 ; i < size ; i++)	{		value = randomNodeIndexs.at(i);		if(value < 0 || value >= size)		{			nodes.at(i)->random = NULL;		}		else		{			nodes.at(i)->random = nodes.at( value );		}	}	return root;}void deleteList(RandomListNode* head){	RandomListNode* node;	while(head)	{		node = head->next;		delete head;		head = node;	}}//打印的时候我们按照第一行直接是原始链表，下面第二行是随意指向的部分，如果没有返回为空void printList(RandomListNode* head){	if(!head)	{		cout << "no result" << endl;		return;	}	RandomListNode* tempHead = head;	while(head)	{		cout << head->label << " ";		head = head->next;	}	cout << endl;	head = tempHead;	while(head)	{		if(head->random)		{			cout << head->random->label << " ";		}		else		{			cout << "NULL " ; 		}		head = head->next;	}	cout << endl;	head = tempHead;}void process(){	 vector<int> nums;	 int value;	 int num;	 Solution solution;	 vector<int> result;	 vector<int> randomNodeIndexs;	 while(cin >> num )	 {		 nums.clear();		 randomNodeIndexs.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 randomNodeIndexs.push_back(value);		 }		 RandomListNode* head = buildList(nums , randomNodeIndexs);		 RandomListNode* newHead = solution.copyRandomList(head);		 //printList(head);		 printList(newHead);		 deleteList(head);		 deleteList(newHead);	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}