剑指OFFER----面试题35. 复杂链表的复制

链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/submissions/

代码：

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node *copyRandomList(Node *head) {
        for (auto p = head; p;) {
            auto np = new Node(p->val);
            auto next = p->next;
            p->next = np;
            np->next = next;
            p = next;
        }

        for (auto p = head; p; p = p->next->next) {
            if (p->random)
                p->next->random = p->random->next;
        }

        auto dummy = new Node(-1);
        auto cur = dummy;
        for (auto p = head; p; p = p->next) {
            cur->next = p->next;
            cur = cur->next;
            p->next = p->next->next;
        }

        return dummy->next;
    }
};