时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
题目描述
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
思路:
1、复制每个节点,并将复制节点A得到的A1,插入到A的后面
2、遍历链表,找随机指针的指向(A1->random = A->random->next)
3、将原链表与复制链表进行拆分(temp = A->next;A->next = temp->next;A = temp,循环指向此句直到A->next为空)
图示例:
代码如下:
/* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */ class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { if(pHead == NULL) return NULL; //复制每个节点 RandomListNode* currNode = pHead; while(currNode) { RandomListNode* node = new RandomListNode(currNode->label); node->next = currNode->next; currNode->next = node; currNode = node->next; } //找随机指针的指向 currNode= pHead; while(currNode) { RandomListNode *node = currNode->next; if(currNode->random) { node->random = currNode->random->next; } currNode = node->next; } //拆分 RandomListNode *pCloneHead = pHead->next; RandomListNode *temp; currNode = pHead; while(currNode->next) { temp = currNode->next; currNode->next = temp->next; currNode = temp; } return pCloneHead; } };
原文链接: https://www.cnblogs.com/whiteBear/p/12561965.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/337385
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!