### 這道題目來自《劍指 offer 》第二版面試題35。復雜鏈表中，每個節點除了有 next 指針外，還有一個指向兄弟的指針 sibling。以下是書中鏈表的聲明：
```
struct ComplexListNode {
int m_nValue;
ComplexListNode *m_pNext;
ComplexListNode *m_pSibling;
};
```
思路：要做到O(n)的時間并不使用額外的輔助空間實現，書中分為三步實現：
1. 復制原始鏈表的每個節點 N 并創建新節點 N<sup>'</sup>，再把N<sup>'</sup>鏈接到 N 的后面。
2. 設置復制出來的節點的 m_pSibling。
3. 拆分鏈表。
以下是代碼實現：
```
// 第一步
void CloneNodes(ComplexListNode *pHead)
{
ComplexListNode *pNode = pHead;
while (pNode != nullptr) {
ComplexListNode *pCloned = new ComplexListNode();
pCloned->m_nValue = pNode->m_nValue;
pCloned->m_pNext = pNode->m_pNext;
pCloned->m_pSibling = nullptr;
pNode->m_pNext = pCloned;
pNode = pCloned->m_pNext;
}
}
// 第二步
void ConnectSiblingNodes(ComplexListNode *pHead)
{
ComplexListNode *pNode = pHead;
while (pNode != nullptr) {
ComplexListNode *pCloned = pNode->m_pNext;
if (pNode->m_pSibling != nullptr) {
pCloned->m_pSibling = pNode->m_pSibling->m_pNext;
}
pNode = pCloned->m_pNext;
}
}
// 第三步
ComplexListNode* ReconnectNodes(ComplexListNode *pHead)
{
ComplexListNode *pNode = pHead;
ComplexListNode *pClonedHead = nullptr;
ComplexListNode *pClonedNode = nullptr; // 每一步保存復制鏈表的尾部
if (pNode != nullptr) {
pClonedHead = pClonedNode = pNode->m_pNext;
pNode->m_pNext = pClonedNode->m_pNext;
pNode = pNode->m_pNext;
}
while (pNode != nullptr) {
pClonedNode->m_pNext = pNode->m_pNext;
pClonedNode = pClonedNode->m_pNext;
pNode->m_pNext = pClonedNode->m_pNext;
pNode = pNode->m_pNext;
}
return pClonedHead;
}
// 綜合
ComplexListNode* Clone(ComplexListNode *pHead)
{
CloneNodes(pHead);
ConnectSiblingNodes(pHead);
return ReconnectNodes(pHead);
}
```