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

自己思考只想出hash表一种解法，参考精华题解的思路给出不使用额外空间的解法：

• 第一次遍历：复制：在原链表的每一个节点后插入使用该节点复制的新节点，这样原链表节点的next指向其复制的节点，而复制节点的next指向原链表节点的下一个节点。
• 第二次遍历：处理random指针：如果原链表节点的random指针为空，则其next节点指向的复制节点的random指针也设置为空；否则指向原链表节点->random->next，即为原链表节点的random指针的复制节点。
• 第三次遍历：分离两个链表，因为不分离会判错“原链表不可用”。

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if (!pHead) return pHead;
        RandomListNode* now = pHead;
        while (now) {
            RandomListNode* tmp = new RandomListNode(now->label);
            tmp->next = now->next;
            now->next = tmp;
            now = tmp->next;
        }
        now = pHead;
        while (now) {
            now->next->random = now->random? now->random->next: nullptr;
            now = now->next->next;
        }
        now = pHead->next;
        RandomListNode* old = pHead, *res = now;
        while (old) {
            if (old->next) old->next = old->next->next;
            if (now->next) now->next = now->next->next;
            old = old->next;
            now = now->next;
        }
        return res;
    }
};