题目描述

请实现一个函数可以复制一个复杂链表。

在复杂链表中，每个结点除了有一个指针指向下一个结点外，还有一个额外的指针指向链表中的任意结点或者null。

样例

注意：

函数结束后原链表要与输入时保持一致。

算法

(虚拟头结点，复刻)

1. 第一步，将原链表中的每个节点都复制一下，复制到其原样本的后面(next)
2. 第二步，判断原链表中的原节点是否有random指针，有的话，将原节点的random指针指向的节点的复刻节点与原节点的复刻值的random指针指向的节点连接在一起，这样就可以将random指针也复制。代码是p->random->next = p->next->random。复刻的节点是不能破坏原链表的，所以不能p->random = p->next->random。因为最后要抽取新链表，所以一切处理都是针对复刻链表执行的。
3. 最后建立一个虚拟头结点dummy来抽取新链表，cur指针表示当前dummy的这个链表的尾节点在哪个位置。
4. 因为不能破坏原链表，所以我们不能在for()循环中直接让p = p->next，因为for()的判断条件中是p = p->next，这样子，原链表中的节点的next就指向了其复制节点。
5. 解决方案是for()的判断条件中还是p = p->next，只不过在for()循环体中，更新的是p->next = p->next->next，这样，p在更新的时候，就是 原链表的下一个节点了。(比较绕，建议画个图就理解了。。

时间复杂度

$O(n)$
虽然遍历了3次，但是每次的时间复杂度都是$O(n)$的，所以总的时度也是$O(n)$的。

C++ 代码

/**
 * Definition for singly-linked list with a random pointer.
 * struct ListNode {
 *     int val;
 *     ListNode *next, *random;
 *     ListNode(int x) : val(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        if(!head || !head->next) return head;
        for(auto p = head; p;)
        {
            auto next = p->next;
            auto np = new ListNode(p->val);
            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;

        ListNode *dummy = new ListNode(-1);
        // dummy->next = head->next;                // **1
        auto cur = dummy;
        for(auto p = head; p; p = p->next)          // **2
        {
            cur->next = p->next;
            cur = cur->next;
            p->next = p->next->next;                // **2
        }

        return dummy->next;

    }
};