输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
此方法为暴力破解大法,时间复杂度n^2,但是秒过剑指offer,不明白的可以私我。
/* 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){ return NULL; } RandomListNode* pHead1 = pHead; RandomListNode* ph = (RandomListNode*)malloc(sizeof(RandomListNode));//开一个新空间 RandomListNode* ph1 = ph; RandomListNode* ph2 = ph; int n = 0,k=0; //先搞定next的指向复制,下一步暴力遍历 while(pHead1){ ph1->label = pHead1->label; if(pHead1->next){ ph1->next = (RandomListNode*)malloc(sizeof(RandomListNode)); ph1->random = (RandomListNode*)malloc(sizeof(RandomListNode)); ph1 = ph1->next; } pHead1 = pHead1->next; n++; } ph1 = NULL; pHead1 = pHead; ph1 = ph; //暴力遍历random的位置。 while(pHead1){ ph2 = ph; k = parition(pHead1->random);//确定此时random 到链表结束的个数 for(int i = 0;i<n-k;i++){//n-k 才是在链表中的位置 并用ph2存储 ph2 = ph2->next; } ph1->random = ph2;//完成了random的复制 ph1 = ph1->next; pHead1 = pHead1->next; } return ph; } int parition(RandomListNode* p){ int k=0; while(p){ k++; p = p->next; } return k; } };