非hashmap和旧链表中创建新链表
简单来说,就是创建两个新vector存储原链表的label和random->label;
然后开始按照label创建新链表,创建完新链表之后,遍历新链表,对于每一个节点,通过判断random->label的值来重新遍历来找到先前连接关系的那个点,然后进行连接。
复杂度为n^2;
/* 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 pHead; vector<int>lab,ran; RandomListNode* now=pHead; while(now){ lab.push_back(now->label); if(now->random){ ran.push_back(now->random->label); }else ran.push_back(0); now=now->next; } //第一次遍历,此前为旧链表的label和random分别存储到两个vector中进行存储。 RandomListNode* head=new RandomListNode(lab[0]),*tem=head; for(int i=1;i<lab.size();i++){ tem->next=new RandomListNode(lab[i]); tem=tem->next; } //创建新链表,按照之前的label vector复制。 tem=head; RandomListNode* tes; for(int i=0;i<ran.size();i++){ if(ran[i]){ tes=head; for(int j=0;j<ran.size();j++){ if(tes->label==ran[i]){ tem->random=tes; break; } tes=tes->next; } } tem=tem->next; } return head; } };