用C++ 實現(xiàn)復雜鏈表的復制

    首先我們先來看一下復雜鏈表的結(jié)構(gòu)：

    這個鏈表不能直接進行復制，如果我們對其進行直接復制將會發(fā)現(xiàn)復制后的鏈表的random依舊指向之前鏈表的位置，并沒有指向自身的某個節(jié)點。因此，我們需要好好分析一下。

方案一：

    我們可以一個節(jié)點一個節(jié)點的進行復制，并將復制后的節(jié)點放到原節(jié)點的后邊。這樣就形成了一個這樣的鏈表：

    然后我們將復制后的節(jié)點指向原節(jié)點random指針指向的位置的下一個位置，遍歷完整個鏈表。接下來最重要的是將鏈表按照奇偶的不同拆分為兩個獨立的鏈表便可等到與原鏈表一樣的鏈表。

方案二：

    我們首先讓當前位置指向head，然后判斷head的random是否為空，如果為空直接復制，若不為空，則需要先記住當前節(jié)點，然后向后遍歷，引入計數(shù)器，遍歷一次計數(shù)器++；直到找到與random相等的節(jié)點，然后將你要復制的鏈表的當前位置以計數(shù)器--,向后遍歷，找到之后將記住的當前節(jié)點的random指向找到的節(jié)點。依次遍歷即可。

    如果要將random指向自身的某個節(jié)點，我們需要記錄random與random指向節(jié)點

比較方案一與方案二：我們將會發(fā)現(xiàn)方案一的空間復雜度小，實現(xiàn)比較簡單。方案二的空間復雜度大，代碼比較冗余，但容易想到。

下面我們來看一下他們各自的代碼：

方案一：

	ComplexList* Listcpy2(ComplexList* cl)
	{
		Node<T>* cur=cl->_head;
		//復制鏈表
		while(cur)
		{
			Node<T>* tmp=new Node(cur->_data);
			tmp->_next=cur->_next;
			cur->_next=tmp;
			cur=tmp->_next;
		}
		cur=cl->_head;
		//置它的random
		while(cur)
		{
			if(cur->_random!=NULL)
			{
				Node<T>* next=cur->_next;
				next->_random=cur->_random->_next;
				cur=cur->_next->_next;
			}			
		}
		cur=cl->_head;
		Node<T>* newhead=NULL;
		Node<T>* newtail=NULL;
		//將奇偶位置的節(jié)點拆分成兩個鏈表
		if(cur)//置頭結(jié)點和尾節(jié)點
		{
			newhead=newtail=cur->_next;
			cur->_next=newhead->_next;
			cur=cur->_next;
		}
		while(cur)
		{
			newtail->_next=cur->_next;
			newtail=newtail->_next;
			cur->_next=newtail->_next;
			cur=cur->_next;
		}
		return newhead;

	}

方案二：

	ComplexList& ListCpy(ComplexList& cl)
	{   
		Node<T>* cur=cl._head;
	    Node<T>* cur1=_head;
		while(cur->_next!=NULL)
		{	
			cur1->_data=cur->_data;
			cur1->_next=cur->_next;
			if(cur->_random==NULL)
			{			
				cur1->_random=NULL;
			}
			else
			{
				Node<T>* cur4=cur;
				int count=1;
				cur4=cur->_next;
				//遍歷找出C1當前節(jié)點的random指針指向的位置，并用一個計數(shù)
				//器記錄遍歷的次數(shù)
				while(cur->_random!=cur4)
				{
					if(cur4->_next==NULL)
					{
						cur4->_next=_head;
						count++;
					}
					else 
					{
						count++;
						
					}
					cur4=cur4->_next;
				}
				//通過對計數(shù)器的--；找到this當前節(jié)點random的指針位置，并
				//賦值
				Node<T>* cur2=cur1;
				while(count)
				{
					cur2=cur2->_next;
					if(cur2==NULL)
					{
						cur2=_head;
					}
					count--;
				}
				cur1->_random=cur2;
			}
			//讓當前指針指向下一個位置
			cur=cur->_next;
			cur1=cur1->_next;
			//在上面的代碼中，我們有可能改掉了C1的最后一個節(jié)點的next,讓它指向                        //了第一個節(jié)點，所以此處將其的next重新置空,否則整個鏈表將會變成循                        //環(huán)鏈表
			if(cur->_next==_head)
			{
				cur->_next=NULL;
			}
		}
		return *this;
	}

最后博主再來講一個函數(shù)，是將鏈表節(jié)點的random指針指向位置的函數(shù)，也就是設(shè)置random的函數(shù)

void SetRandom(ComplexList& cl,int n=-1,int count=0)//這里的參數(shù)n的表示相對頭節(jié)點有幾個位//置的節(jié)點，也就是我們要設(shè)置的節(jié)點。count表示相對設(shè)置的節(jié)點的位置即相對位置的節(jié)點向后指向//count次，找到random的位置。
	{
		Node<T>* cur1=_head;
		if(n==-1||count==0)
		{
			return;
		}
		while(n--)
		{
			cur1=cur1->_next;
		}
		Node<T>* cur2=cur1;
		while(count--)
		{				
			if(cur2->_next==NULL)
			{
				cur2=_head;
			}
			else
			{
				cur2=cur2->_next;
			}
		}
		cur1->_random=cur2;
	}