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

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

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

方法二：換一種思路，在不用輔助空間的情況下實現(xiàn)O(n)的時間效率。第三種方法的第一步仍然是根據(jù)原始鏈表的每個結(jié)點N，創(chuàng)建對應的N’。這一次，我們把N’鏈接在N的后面。實例中的鏈表經(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è)置我們復制出來的鏈表上的結(jié)點的m_pSibling。假設(shè)原始鏈表上的N的m_pSibling指向結(jié)點S，那么其對應復制出來的N’是N->m_pNext，同樣S’也是S->m_pNext。這就是我們在上一步中把每個結(jié)點復制出來的結(jié)點鏈接在原始結(jié)點后面的原因。有了這樣的鏈接方式，我們就能在O(1)中就能找到每個結(jié)點的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;

	}

}

第三步是把這個長鏈表拆分成兩個：一個原始鏈表，還有一個就是我們復制的鏈表了。

???

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

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

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

}

?