淺談復雜鏈表的復制

鏈表是一種很常見的數據結構，單鏈表、雙向鏈表、循環鏈表和復雜鏈表都是其衍生物。復雜鏈表之所以命名為復雜鏈表，也正是由于其結構的復雜。它比其他其他種類的鏈表多了一個指針域，這個指針域可以指向鏈表中的任一結點，也可以為空。

其結構定義如下：

struct ComplexNode
{
	DataType _data;
	struct ComplexNode * _next;
	struct ComplexNode * _random;//隨機域
};

結構示例：

ps：藍色指針為next域，紅色為random域。

接下來就要思考如何復制了。復制一個單鏈表很簡單，所以問題的難點就在于如何復制它的隨機指針域。

首先想到的就是先將原始鏈表的每一個結點復制下來，并用next連接，使其先成為一個單鏈表。接下來，就是考慮如何復制random域了。由于這個指針可以指向鏈表中的任何一個指針，所以必須從頭遍歷整個鏈表才可以找到這個指針。可以采取這樣一種方式，就是先遍歷原始鏈表，數出其到random是多少步，然后記下，讓復制的鏈表也進行相同的步數找到其random指向的結點。這樣就可以復制random指針了。這種方法需要對n個結點遍歷n次才可以。時間復雜度為O（n^2）。

嘗試對其進行優化。

Step1——>要做的還是將鏈表的每個結點復制下來，并將其連在原始鏈表的后面，先將其random域賦為空。

代碼實現：

void CopyNode(ComplexNode *pHead)
{
	ComplexNode *pNode=pHead;
	while(pNode!=NULL)
	{
		ComplexNode *pCopy=new ComplexNode;
		pCopy->_data=pNode->_data;
		pCopy->_next=pNode->_next;
		pCopy->_random=NULL;
		pNode->_next=pCopy;
		pNode=pCopy->_next;
	}
}

Step2——>拷貝random域。由于已經將復制的結點連接在相應的原始結點的后面。所以復制的結點的random域也是原始結點對應的random域的下一個指針。

代碼實現;

void ConnectRandom(ComplexNode *pHead)
{
	ComplexNode *pNode=pHead;
	while(pNode!=NULL)
	{
		ComplexNode *pCopy=pNode->_next;
		if(pNode->_random!=NULL)
		{
			pCopy->_random=pNode->_random->_next;
		}
		pNode=pCopy->_next;
	}
}

Step3——>將鏈表拆分為兩個部分，也就是將原始鏈表和復制鏈表分開。返回的是復制的鏈表。

ComplexNode* SplitList(ComplexNode *pHead)
{

    ComplexNode *pCloneHead = pHead->_next;
    ComplexNode *tmp;	   
    ComplexNode *cur = pHead;
        while(cur->_next)
		{
            tmp = cur->_next;
            cur->_next =tmp->_next;
            cur = tmp;
        }
        return pCloneHead;
}