完成復雜鏈表的復制

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

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

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

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

?

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;

	}
}

第二步是設置我們復制出來的鏈表上的結點的m_pSibling。假設原始鏈表上的N的m_pSibling指向結點S，那么其對應復制出來的N’是N->m_pNext，同樣S’也是S->m_pNext。這就是我們在上一步中把每個結點復制出來的結點鏈接在原始結點后面的原因。有了這樣的鏈接方式，我們就能在O(1)中就能找到每個結點的m_pSibling了。例子中的鏈表經過這一步，就變成如下結構了：

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

}

?