首页 > 代码库 > 【编程题目】复杂链表的复制☆
【编程题目】复杂链表的复制☆
76.复杂链表的复制（链表、算法）
题目：有一个复杂链表，其结点除了有一个 m_pNext 指针指向下一个结点外，
还有一个 m_pSibling 指向链表中的任一结点或者 NULL。其结点的 C++定义如下：
struct ComplexNode
{
int m_nValue;
ComplexNode* m_pNext;
ComplexNode* m_pSibling;
};
请完成函数 ComplexNode* Clone(ComplexNode* pHead)，以复制一个复杂链表。
思路：先按照m_pNext复制，再依次遍历链表找m_pSibling
#include <stdio.h>#include <stdlib.h>typedef struct ComplexNode{ int m_nValue; ComplexNode* m_pNext; ComplexNode* m_pSibling;}ComplexNode;ComplexNode* Clone(ComplexNode* pHead) //完全复制{ if (pHead == NULL) { return NULL; } //先复制头结点 ComplexNode* chead = (ComplexNode*)malloc(sizeof(ComplexNode)); chead->m_nValue = http://www.mamicode.com/pHead->m_nValue; chead->m_pNext = NULL; chead->m_pSibling = NULL; ComplexNode* x = pHead->m_pNext; ComplexNode* y = chead; while(x != NULL) //按照next信息先创建所有的点并连接 { y->m_pNext = (ComplexNode*)malloc(sizeof(ComplexNode)); y->m_pNext->m_nValue = http://www.mamicode.com/x->m_nValue; y->m_pNext->m_pNext = NULL; y->m_pNext->m_pSibling = NULL; x = x->m_pNext; y = y->m_pNext; } //复制m_pSibling的指向 x = pHead; y = chead; while (x != NULL) { if (x->m_pSibling == NULL) //空指针直接复制 { y->m_pSibling = NULL; } else //非空指针 从头查找指向第几个节点 { if (pHead == x->m_pSibling) { y->m_pSibling = chead; } else { ComplexNode * xx = pHead; ComplexNode * yy = chead; while (xx->m_pNext != x->m_pSibling) { xx = xx->m_pNext; yy = yy->m_pNext; } y->m_pSibling = yy->m_pNext; } } x = x->m_pNext; y = y->m_pNext; } return chead;}void createList(ComplexNode* &pHead) //创建并添加next间关系{ int data; scanf("%d", &data); if (data != 0) { pHead = (ComplexNode*)malloc(sizeof(ComplexNode)); pHead->m_nValue =http://www.mamicode.com/ data; pHead->m_pNext = NULL; pHead->m_pSibling = NULL; createList(pHead->m_pNext); }}void addsibling(ComplexNode* pHead) //添加pSibling间关系{ int len = 0; ComplexNode* x = pHead; while (x != NULL) { len++; x = x->m_pNext; } x = pHead; while (x != NULL) { int n = 0; //数字表示p_Sibling指向链表中的第n个结点 printf("please input a number between 1 - %d or 0(means NULL)", len); scanf("%d", &n); if (n == 0) { x->m_pSibling = NULL; } else { ComplexNode* y = pHead; n = n - 1; while (n != 0) { y = y->m_pNext; n--; } x->m_pSibling = y; } x = x->m_pNext; }}int main(){ ComplexNode* pHead = NULL; createList(pHead); addsibling(pHead); ComplexNode* cHead = Clone(pHead); return 0;}
网上看答案 发现自己的方法很复杂，有一种很巧妙的方法：
http://blog.csdn.net/zhaojinjia/article/details/9313275
方法三：
比较巧妙，只需遍历3次链表，时间代价为O(n)，空间代价为0，分3步
1：遍历一遍原始链表，复制结点N对应的N‘，将其插入到结点N的后面，如下图所示
2：确定每个m_pSibling指针的指向，只需遍历一遍链表即可确定每个结点的m_pSibling指针的指向，得到如下图结构
3：再次遍历一遍，将原始链表和复制链表分开，奇数为原始链表，偶数为复制链表，得到如下图型
这个网站上的代码可能略有一点问题。
不过知道思路后，写代码就很容易了。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。