淺談復(fù)雜鏈表的復(fù)制

鏈表是一種很常見的數(shù)據(jù)結(jié)構(gòu)，單鏈表、雙向鏈表、循環(huán)鏈表和復(fù)雜鏈表都是其衍生物。復(fù)雜鏈表之所以命名為復(fù)雜鏈表，也正是由于其結(jié)構(gòu)的復(fù)雜。它比其他其他種類的鏈表多了一個指針域，這個指針域可以指向鏈表中的任一結(jié)點，也可以為空。

其結(jié)構(gòu)定義如下：

struct ComplexNode
{
	DataType _data;
	struct ComplexNode * _next;
	struct ComplexNode * _random;//隨機(jī)域
};

結(jié)構(gòu)示例：

ps：藍(lán)色指針為next域，紅色為random域。

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

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

嘗試對其進(jìn)行優(yōu)化。

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

代碼實現(xiàn)：

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域。由于已經(jīng)將復(fù)制的結(jié)點連接在相應(yīng)的原始結(jié)點的后面。所以復(fù)制的結(jié)點的random域也是原始結(jié)點對應(yīng)的random域的下一個指針。

代碼實現(xiàn);

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——>將鏈表拆分為兩個部分，也就是將原始鏈表和復(fù)制鏈表分開。返回的是復(fù)制的鏈表。

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