用C++ 實現復雜鏈表的復制

    首先我們先來看一下復雜鏈表的結構：

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

方案一：

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

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

方案二：

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

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

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

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

方案一：

	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;
		//將奇偶位置的節點拆分成兩個鏈表
		if(cur)//置頭結點和尾節點
		{
			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當前節點的random指針指向的位置，并用一個計數
				//器記錄遍歷的次數
				while(cur->_random!=cur4)
				{
					if(cur4->_next==NULL)
					{
						cur4->_next=_head;
						count++;
					}
					else 
					{
						count++;
						
					}
					cur4=cur4->_next;
				}
				//通過對計數器的--；找到this當前節點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的最后一個節點的next,讓它指向                        //了第一個節點，所以此處將其的next重新置空,否則整個鏈表將會變成循                        //環鏈表
			if(cur->_next==_head)
			{
				cur->_next=NULL;
			}
		}
		return *this;
	}

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

void SetRandom(ComplexList& cl,int n=-1,int count=0)//這里的參數n的表示相對頭節點有幾個位//置的節點，也就是我們要設置的節點。count表示相對設置的節點的位置即相對位置的節點向后指向//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;
	}