完成復(fù)雜鏈表的復(fù)制

題目：有一個(gè)復(fù)雜鏈表，其結(jié)點(diǎn)除了有一個(gè)m_pNext指針指向下一個(gè)結(jié)點(diǎn)外，還有一個(gè)m_pSibling指向鏈表中的任一結(jié)點(diǎn)或者NULL。請(qǐng)完成函數(shù)ComplexNode* Clone(ComplexNode* pHead)，以復(fù)制一個(gè)復(fù)雜鏈表。其結(jié)點(diǎn)的C++定義如下：
?struct ComplexNode
{
??? int m_nValue;
??? ComplexNode* m_pNext;
??? ComplexNode* m_pSibling;
};

下圖是一個(gè)含有5個(gè)結(jié)點(diǎn)的該類型復(fù)雜鏈表。圖中實(shí)線箭頭表示m_pNext指針，虛線箭頭表示m_pSibling指針。為簡(jiǎn)單起見，指向NULL的指針沒有畫出。

方法一：看到這個(gè)問題，我的第一反應(yīng)是分成兩步：第一步是復(fù)制原始鏈表上的每個(gè)鏈表，并用m_pNext鏈接起來；第二步，假設(shè)原始鏈表中的某節(jié)點(diǎn)N的m_pSibling指向結(jié)點(diǎn)S，由于S的位置在鏈表上有可能在N的前面也可能在N的后面，所以要定位N的位置需要從原始鏈表的頭結(jié)點(diǎn)開始找，假設(shè)從原始鏈表的頭結(jié)點(diǎn)開始經(jīng)過s步找到結(jié)點(diǎn)S，那么在復(fù)制鏈表上結(jié)點(diǎn)N的m_pSibling的S’，離復(fù)制鏈表的頭結(jié)點(diǎn)的距離也是s，用這種辦法我們就能為復(fù)制鏈表上的每個(gè)結(jié)點(diǎn)設(shè)置m_pSibling了。對(duì)含有n個(gè)結(jié)點(diǎn)的鏈表，由于定位每個(gè)結(jié)點(diǎn)的m_pSibling都需要從鏈表頭結(jié)點(diǎn)開始經(jīng)過O(n)步才能找到，因此這種方法的總時(shí)間復(fù)雜度是O(n²)。

方法二：換一種思路，在不用輔助空間的情況下實(shí)現(xiàn)O(n)的時(shí)間效率。第三種方法的第一步仍然是根據(jù)原始鏈表的每個(gè)結(jié)點(diǎn)N，創(chuàng)建對(duì)應(yīng)的N’。這一次，我們把N’鏈接在N的后面。實(shí)例中的鏈表經(jīng)過這一步之后變成了：

?

void?CloneNodes(ComplexNode*?pHead)
{
	ComplexNode*?pNode=pHead;
	while(pNode!=NULL)
	{
		ComplexNode*?pCloned=new?ComplexNode();
		pCloned->m_nValue=pNode->m_nValue;
		pCloned->m_pNext=pNode->m_pNext;
		pCloned->m_pSibling=NULL;
		pNode->m_pNext=pCloned;
		pNode=pCloned->m_pNext;

	}
}

第二步是設(shè)置我們復(fù)制出來的鏈表上的結(jié)點(diǎn)的m_pSibling。假設(shè)原始鏈表上的N的m_pSibling指向結(jié)點(diǎn)S，那么其對(duì)應(yīng)復(fù)制出來的N’是N->m_pNext，同樣S’也是S->m_pNext。這就是我們?cè)谏弦徊街邪衙總€(gè)結(jié)點(diǎn)復(fù)制出來的結(jié)點(diǎn)鏈接在原始結(jié)點(diǎn)后面的原因。有了這樣的鏈接方式，我們就能在O(1)中就能找到每個(gè)結(jié)點(diǎn)的m_pSibling了。例子中的鏈表經(jīng)過這一步，就變成如下結(jié)構(gòu)了：

void?ConnectSiblingNodes(ComplexNode*?pHead)
{
	ComplexNode*?pNode=pHead;
	while(pNode)
	{
		ComplexNode*?pCloned=pNode->m_pNext;
		if(pNode->m_pSibling)
			pCloned->m_pSibling=pNode->m_pSibling->m_pNext;
		pNode=pCloned->m_pNext;

	}

}

第三步是把這個(gè)長(zhǎng)鏈表拆分成兩個(gè)：一個(gè)原始鏈表，還有一個(gè)就是我們復(fù)制的鏈表了。

???

ComplexNode*?ReconnectNodes(ComplexNode*?pHead)
{
	ComplexNode*?pNode=pHead;
	ComplexNode*?pClonedHead=NULL;
	ComplexNode*?pClonedNode=NULL;

	if(pNode!=NULL)
	{
		pClonedHead=pClonedNode=pNode->m_pNext;
		pNode->m_pNext=pClonedNode->m_pNext;
		pNode=pNode->m_pNext;
	}

	while(pNode!=NULL)
	{
		pClonedNode->m_pNext=pNode->m_pNext;
		pClonedNode=pClonedNode->m_pNext;

		pNode->m_pNext=pClonedNode->m_pNext;
		pNode=pNode->m_pNext;
	}

	return?pClonedHead;
}

把上面三步合起來，就是復(fù)制鏈表的完整過程：

ComplexNode*?Clone(ComplexNode*?pHead)
{
	CloneNodes(pHead);
	ConnectSiblingNodes(pHead);
	ReconnectNodes(pHead);

}

?