#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;}