### 这道题目来自《剑指 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);
}
```