题解 | #复杂链表的复制#
复杂链表的复制
http://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba
最笨最直接的方法:
- 根据next指针将链表的label值拷贝出来生成新的链表pNode。
- 两个链表同时遍历,填充random
- 每一个元素,内部再两个链表同时遍历
- 找到第一个的random时,第二个链表也指向正确的random,此时赋值给第二个的random
- 注意几个特殊情况:random指向空,random指向自己
本方法的时间复杂度O(n+n^2) = O(n^2);空间复杂度O(1)
/*
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 nullptr;
RandomListNode* p1 = pHead;
// for label and next
RandomListNode* pNode = new RandomListNode(p1->label);
RandomListNode* p2 = pNode;
while(1){
if(p1->next == nullptr){
p2->next = nullptr;
break;
}
RandomListNode* pNew = new RandomListNode(p1->next->label);
p2->next = pNew;
p1 = p1->next;
p2 = p2->next;
}
// for random
p2 = pNode;
p1 = pHead;
while(p2){//p2 loop
if(!p1->random){
p2->random=nullptr;
p2 = p2->next;
p1 = p1->next;
continue;
}
if(p1->random == p1){
p2->random=p2;
p2 = p2->next;
p1 = p1->next;
continue;
}
RandomListNode* cursor1 = pHead;
RandomListNode* cursor2 = pNode;
while(cursor1){
if(p1->random == cursor1){
p2->random = cursor2;
break;
}
cursor1 = cursor1->next;
cursor2 = cursor2->next;
}
p2 = p2->next;
p1 = p1->next;
}
return pNode;
}
};