题解 | #复杂链表的复制#

最笨最直接的方法：

1. 根据next指针将链表的label值拷贝出来生成新的链表pNode。
2. 两个链表同时遍历，填充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;
    }
};