題目：請實現(xiàn)函數(shù)ComplexListNode* Clone(ComplexListNode* pHead),復制一個復雜鏈表怀薛。在復雜鏈表中债鸡，每個結(jié)點除了有一個m_pNext指針指向下一個結(jié)點外濒翻，還有一個m_pSibling指向鏈表中的任意結(jié)點或者NULL翘鸭。結(jié)點的C++定義如下：
struct ComplexListNode{
? ? int m_nValue;
? ? ComplexListNode* m_pNext;
? ? ComplexListNode* m_pSibling;
};
思路1：第一步復制原始鏈表上的每個結(jié)點N創(chuàng)建N‘闷串，然后把這些創(chuàng)建出來的結(jié)點用m_pNext鏈接起來享扔。同時把<N, N'>的配對信息放到一個哈希表中。第二步還是設置復制鏈表上每個結(jié)點的m_pSibling式散。如果在原始鏈表中結(jié)點N的m_pSibling指向結(jié)點S筋遭，那么中復制鏈表中，對于的N'應該指向S'暴拄。
思路2:在不用輔助空間的情況下實現(xiàn)O(n)的時間效率漓滔。第三種方法的第一步仍然是根據(jù)原始鏈表的每個結(jié)點N創(chuàng)建對應的N'。把N'鏈接在N后面乖篷。第二步設置復制出來的結(jié)點的m_pSibling.假設原始鏈表上的N的m_pSibling指向結(jié)點S响驴，那么其對應復制出來的N'是N的m_pNext指向的結(jié)點，同樣S'也是S的m_pNext指向的結(jié)點撕蔼。第三步就是把這個長鏈表拆分成兩個鏈表：把奇數(shù)位置的結(jié)點用m_pNext鏈接起來就是原始鏈表豁鲤，把偶數(shù)位置的結(jié)點用m_pNext鏈接起來就是復制出來的鏈表。
