浅谈复杂链表的复制-创新互联
链表是一种很常见的数据结构,单链表、双向链表、循环链表和复杂链表都是其衍生物。复杂链表之所以命名为复杂链表,也正是由于其结构的复杂。它比其他其他种类的链表多了一个指针域,这个指针域可以指向链表中的任一结点,也可以为空。
成都创新互联主要从事成都网站建设、成都做网站、网页设计、企业做网站、公司建网站等业务。立足成都服务隆尧,十多年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:028-86922220其结构定义如下:
struct ComplexNode { DataType _data; struct ComplexNode * _next; struct ComplexNode * _random;//随机域 };
结构示例:
ps:蓝色指针为next域,红色为random域。
接下来就要思考如何复制了。复制一个单链表很简单,所以问题的难点就在于如何复制它的随机指针域。
首先想到的就是先将原始链表的每一个结点复制下来,并用next连接,使其先成为一个单链表。接下来,就是考虑如何复制random域了。由于这个指针可以指向链表中的任何一个指针,所以必须从头遍历整个链表才可以找到这个指针。可以采取这样一种方式,就是先遍历原始链表,数出其到random是多少步,然后记下,让复制的链表也进行相同的步数找到其random指向的结点。这样就可以复制random指针了。这种方法需要对n个结点遍历n次才可以。时间复杂度为O(n^2)。
尝试对其进行优化。
Step1——>要做的还是将链表的每个结点复制下来,并将其连在原始链表的后面,先将其random域赋为空。
代码实现:
void CopyNode(ComplexNode *pHead) { ComplexNode *pNode=pHead; while(pNode!=NULL) { ComplexNode *pCopy=new ComplexNode; pCopy->_data=pNode->_data; pCopy->_next=pNode->_next; pCopy->_random=NULL; pNode->_next=pCopy; pNode=pCopy->_next; } }
Step2——>拷贝random域。由于已经将复制的结点连接在相应的原始结点的后面。所以复制的结点的random域也是原始结点对应的random域的下一个指针。
代码实现;
void ConnectRandom(ComplexNode *pHead) { ComplexNode *pNode=pHead; while(pNode!=NULL) { ComplexNode *pCopy=pNode->_next; if(pNode->_random!=NULL) { pCopy->_random=pNode->_random->_next; } pNode=pCopy->_next; } }
Step3——>将链表拆分为两个部分,也就是将原始链表和复制链表分开。返回的是复制的链表。
ComplexNode* SplitList(ComplexNode *pHead) { ComplexNode *pCloneHead = pHead->_next; ComplexNode *tmp; ComplexNode *cur = pHead; while(cur->_next) { tmp = cur->_next; cur->_next =tmp->_next; cur = tmp; } return pCloneHead; }
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
标题名称:浅谈复杂链表的复制-创新互联
网站网址:http://scyanting.com/article/pdjgj.html