首页 > 代码库 > 复杂链表的复制
复杂链表的复制
题目：有一个复杂链表，除了有一个m_pNext指针指向下一个结点外，还有一个m_pSibling指向链表中的任一结点或者NULL。结点的C++定义如下：
1 struct ComplexNode2 {3 int m_nValue;4 ComplexNode* m_pNext;5 ComplexNode* m_pSibling;6 };
完成复制链表的函数ComplexNode* Clone(ComplexNode* pHead)。
解答：不使用辅助空间，实现O(n)的效率。分三步：
(1) 对于原始的每个结点N，复制对应的N‘，把N‘链接在N的后面。
(2) 设置复制出来的结点的m_pSibling。
(3) 拆分链表。
第一步的代码：
1 void CloneNodes(ComplexNode* pHead) 2 { 3 ComplexNode *pNode = pHead; 4 while (pNode != NULL) 5 { 6 ComplexNode* pCloned = new ComplexNode(); 7 pCloned->m_nValue = http://www.mamicode.com/pNode->m_nValue; 8 pCloned->m_pNext = pNode->m_pNext; 9 pCloned->m_pSibling = NULL;10 11 pNode->m_pNext = pCloned;12 pNode = pNode->m_pNext;13 }14 }
第二步的代码：
1 void ConnectSiblingNodes(ComplexNode* pHead) 2 { 3 ComplexNode* pNode = pHead; 4 while (pNode != NULL) 5 { 6 ComplexNode* pCloned = pNode->m_pNext; 7 if (pNode->m_pSibling != NULL) 8 { 9 pCloned->m_pSibling = pNode->m_pSibling->m_pNext;10 }11 pNode = pCloned->m_pNext;12 }13 }
第三步的代码：
1 ComplexNode* ReconnectNodes(ComplexNode* pHead) 2 { 3 ComplexNode* pNode = pHead; 4 ComplexNode* pClonedHead = NULL; 5 ComplexNode* pClonedNode = NULL; 6 7 if (pNode != NULL) 8 { 9 pClonedHead = pClonedNode = pNode->m_pNext;10 pNode->m_pNext = pClonedNode->m_pNext;11 pNode = pNode->m_pNext;12 }13 14 while (pNode != NULL)15 {16 pClonedNode->m_pNext = pNode->m_pNext;17 pClonedNode = pClonedNode->m_pNext;18 19 pNode->m_pNext = pClonedNode->m_pNext;20 pNode = pNode->m_pNext;21 }22 23 return pClonedHead;24 }
把三步合起来，就是复制链表的完整过程：
1 ComplexNode* Clone(ComplexNode* pHead)2 {3 CloneNodes(pHead);4 ConnectSiblingNodes(pHead);5 return ReconnectNodes(pHead);6 }
参考：http://zhedahht.blog.163.com/blog/static/254111742010819104710337/
复杂链表的复制
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。