复杂链表的复制

Q:有一个复杂链表，其结点除了有一个m_pNext指针指向下一个结点外，还有一个m_pSibling指向链表中的任一结点或者NULL。请完成函数ComplexNode* Clone(ComplexNode* pHead)，以复制一个复杂链表。

---

A:一开始想这道题毫无思路，如果蛮来，首先创建好正常的链表，然后考虑sibling这个分量，则需要O(n^2)的时间复杂度，然后一个技巧便可以巧妙的解答此题。看图便知。

首先是原始的链表

然后我们还是首先复制每一个结点N为N*，不同的是我们将N*让在对应的N后面，即为

然后我们要确定每一个N*的sibling分量，非常明显，N的sibling分量的next就是N*的sibling分量。

最后，将整个链表拆分成原始链表和拷贝出的链表。

代码如下：

#include <iostream> using namespace std; typedef struct ComplexListNode{ int val; ComplexListNode* next; ComplexListNode* sibing; }; //第一步：复制next域 void copyNodes(ComplexListNode *pHead){ if (pHead == NULL) return; ComplexListNode* pNode=pHead; while (pNode != NULL){ ComplexListNode* pCloneNode = new ComplexListNode(); pCloneNode->next = pNode->next; pCloneNode->val = pNode->val; pCloneNode->sibing = NULL; pNode->next = pCloneNode; pNode = pCloneNode->next; } } //第二步：复制sibing域 void copySibingNodes(ComplexListNode *pHead){ if (pHead == NULL) return; ComplexListNode* pNode = pHead; ComplexListNode* pCloneNode; while (pNode != NULL){ pCloneNode = pNode->next; if (pNode->sibing != NULL){ pCloneNode->sibing = pNode->sibing->next; } pNode = pCloneNode->next; } } //第三步：把长链表拆开成两个链表，奇数位置的结点和偶数位置的结点 ComplexListNode* ReconnectNode(ComplexListNode *pHead){ ComplexListNode* pNode = pHead; ComplexListNode* pCloneHead = NULL; ComplexListNode* pCloneNode = NULL; if (pNode != NULL){ pCloneHead = pCloneNode = pNode->next; pNode->next = pCloneNode->next; pNode = pNode->next; } while (pNode != NULL){ pCloneNode->next = pNode->next; pCloneNode = pCloneNode->next; pNode->next = pCloneNode->next; pNode = pNode->next; } return pCloneHead; }