題目:有一個復(fù)雜鏈表,其結(jié)點除了有一個m_pNext指針指向下一個結(jié)點外,還有一個m_pSibling指向鏈表中的任一結(jié)點或者NULL。請完成函數(shù)ComplexNode*
Clone(ComplexNode* pHead),以復(fù)制一個復(fù)雜鏈表。其結(jié)點的C++定義如下:
?struct ComplexNode
{
??? int m_nValue;
??? ComplexNode* m_pNext;
??? ComplexNode* m_pSibling;
};
下圖是一個含有5個結(jié)點的該類型復(fù)雜鏈表。圖中實線箭頭表示m_pNext指針,虛線箭頭表示m_pSibling指針。為簡單起見,指向NULL的指針沒有畫出。
方法一:看到這個問題,我的第一反應(yīng)是分成兩步:第一步是復(fù)制原始鏈表上的每個鏈表,并用m_pNext鏈接起來;第二步,假設(shè)原始鏈表中的某節(jié)點N的m_pSibling指向結(jié)點S,由于S的位置在鏈表上有可能在N的前面也可能在N的后面,所以要定位N的位置需要從原始鏈表的頭結(jié)點開始找,假設(shè)從原始鏈表的頭結(jié)點開始經(jīng)過s步找到結(jié)點S,那么在復(fù)制鏈表上結(jié)點N的m_pSibling的S’,離復(fù)制鏈表的頭結(jié)點的距離也是s,用這種辦法我們就能為復(fù)制鏈表上的每個結(jié)點設(shè)置m_pSibling了。對含有n個結(jié)點的鏈表,由于定位每個結(jié)點的m_pSibling都需要從鏈表頭結(jié)點開始經(jīng)過O(n)步才能找到,因此這種方法的總時間復(fù)雜度是O(n2)。
方法二:換一種思路,在不用輔助空間的情況下實現(xiàn)O(n)的時間效率。第三種方法的第一步仍然是根據(jù)原始鏈表的每個結(jié)點N,創(chuàng)建對應(yī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è)置我們復(fù)制出來的鏈表上的結(jié)點的m_pSibling。假設(shè)原始鏈表上的N的m_pSibling指向結(jié)點S,那么其對應(yīng)復(fù)制出來的N’是N->m_pNext,同樣S’也是S->m_pNext。這就是我們在上一步中把每個結(jié)點復(fù)制出來的結(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; } }
第三步是把這個長鏈表拆分成兩個:一個原始鏈表,還有一個就是我們復(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); }
?